Main memory is a critical resource when processing long-running queries over data streams with state intensive operators. In this work, we investigate state spill strategies that handle run-time memory shortage when processing such complex queries by selectively pushing operator states into disks. Unlike previous solutions which all focus on one single operator only, we instead target queries with multiple state intensive operators. We observe an interdependency among multiple operators in the query plan when spilling operator states. We illustrate that existing strategies, which do not take account of this interdependency, become largely ineffective in this query context. Clearly, a consolidated plan level spill strategy must be devised to address this problem. Several data spill strategies are proposed in this paper to maximize the run-time query throughput in memory constrained environments. The bottom-up state spill strategy is an operator-level strategy that treats all data in one operator state equally. More sophisticated partition-level data spill strategies are then proposed to take different characteristics of the input data into account, including the local output, the global output and the global output with penalty strategies. All proposed state spill strategies have been implemented in the D-CAPE continuous query system. The experimental results confirm the effectiveness of our proposed strategies. In particular, the global output strategy and the global output with penalty strategy have shown favorable results as compared to the other two more localized strategies.

Materialized views defined over distributed data sources are critical for many applications to ensure efficient access, reliable performance, and high availability. Materialized views need to be maintained upon source updates since stale view extents may not serve well or may even mislead user applications. Thus, view maintenance performance is one of the keys to the success of these applications. In this work, we investigate two maintenance strategies, extended batching and view graph transformation, for maintaining general join views where join conditions may exist between any pairs of data sources possibly with cycles. Many choices are available for maintaining cyclic join views. We thus propose a cost-driven view maintenance framework which generates optimized maintenance plans tuned to the environmental settings. The proposed framework has been implemented in the TxnWrap system. Experimental studies illustrate that our proposed optimization techniques significantly improve the view maintenance performance in a distributed environment.

Efficient continuous query processing is critical for many applications, including monitoring remote sensors network traffic management, and online transaction processing. To overcome resource limitations and achieve real-time responsiveness, continuous query systems research focuses on issues such as punctuation-driven operator-state purging [4], load shedding, operator scheduling [7] and plan optimization and on-line migration [9]. However, when real-time yet accurate results are critical such as in stock market analysis, then there is a limitation to what any of the above optimization techniques can accomplish. Hence, distributed processing must be applied to support required scalability. It has been already proven in traditional database systems [3] that distributed processing results in high scale-up and speed-up capabilities due to aggregated resources. The design of a distributed continuous query system is characterized by an extra complexity, considered in the design of our D-Cape engine. In such a system, data streams may be infinite and initial cost statistics about the data streams are typically unknown. Moreover, cost statistics continue to change over time. Our research on distributed stream processing addresses two critical questions: (1) How to initially distribute query plans given little or possibly no cost information, and (2) How to efficiently adapt the query distribution corresponding to runtime environmental changes. Even though research is now under way in designing distributed continuous query systems [2], [1], results to date, as far as we know, are based on simulations. Our work offers empirical results of distributed continuous query processing using an actual software system [5], [6]. D-Cape, a distributed continuous query processing architecture, employs stream query engines over a cluster of shared-nothing processors. We employ a dedicated distribution manager to manage

Maintaining materialized views that have join conditions between arbitrary pairs of data sources possibly with cycles is critical for many applications. In this paper, we model view maintenance as the process of answering a set of inter-related distributed multi-join queries. We illustrate two strategies for maintaining as well as optimizing such general join views. We propose a cost-driven view maintenance framework which generates optimized maintenance plans tuned to a given environmental settings. This framework can significantly improve view maintenance performance especially in a distributed environment.

Materialized views defined over distributed data sources are a well recognized technology for modern applications. State-of the-art incremental view maintenance requires O(n2) or more maintenance queries to remote data sources with n being the number of data sources in the view definition. In this poster, we illustrate basic ideas of novel view maintenance strategies that dramatically reduce the number of maintenance queries. Such reduction brings the tradeoff between the number of maintenance queries and the complexity of each query. These algorithms have been implemented in a working prototype system. Experimental studies illustrate major performance improvement in terms of total processing time compared with existing batch algorithms.

Materialized views can be maintained by submitting maintenance queries to the data sources. However, the query results may be erroneous due to concurrent source updates. State-of-the-art maintenance strategies typically apply compensations to resolve such conflicts and assume all source schemata remain stable over time. In a loosely coupled dynamic environment, the sources may autonomously change not only their data but also their schema or semantics. Consequently, either the maintenance or the compensation queries may be broken. Unlike compensation-based approaches found in the literature, we instead model the complete materialized view maintenance process as a view maintenance transaction (VM_Transaction). This way, the anomaly problem can be rephrased as the serializability of VM_Transactions. To achieve VM_Transaction serializability, we propose a multiversion concurrency control algorithm, called TxnWrap , which is shown to be the appropriate design for loosely coupled environments with autonomous data sources. TxnWrap is complementary to the maintenance algorithms proposed in the literature, since it removes concurrency issues from consideration allowing the designer to focus on the maintenance logic. We show several optimizations of TxnWrap, in particular, (1) space optimizations on versioned data materialization and (2) parallel maintenance scheduling. With these optimizations, TxnWrap even outperforms state-of-the-art view maintenance solutions in terms of refresh time. Further, several design choices of TxnWrap are studied each having its respective advantages for certain environmental settings. A correctness proof based on transaction theory for TxnWrap is also provided. Last, we have implemented TxnWrap. The experimental results confirm that TxnWrap achieves predictable performance under a varying rate of concurrency.

Data warehouse view maintenance is an important issue due to the growing use of warehouse technology for information integration and data analysis. Given the dynamic nature of modern distributed environments, both data updates and schema changes are likely to occur in different data sources. In applications that the real-time refreshment of data warehouse extent under source changes is not critical, the source updates are usually maintained in a batch fashion to reduce the maintenance overhead. However, most prior work can only deal with batch source data updates. In this paper, we provide a solution strategy that is capable of batching both source data updates and schema changes. We propose techniques to first preprocess the initial source updates to summarize delta changes for each source. We then design a view adaptation algorithm to adapt the warehouse view under these delta changes. We have implemented our solutions and incorporated into an existing data warehouse prototype system. The experimental studies demonstrate excellent performance achievable by our batch techniques.