Quality-driven disorder handling for concurrent windowed stream queries with shared operators

Handling timestamp-disorder among stream tuples is a basic requirement for data stream processing, and involves an inevitable tradeoff between the latency and the quality of stream query results. To meet the tradeoff requirements of diverse streaming applications, the approach of buffer-based, quality-driven disorder handling (QDDH) was proposed recently, which aims to minimize sizes of stream-sorting buffers, thus the result latency, while honoring user-specified result-quality requirements. Previous work on QDDH focuses only on individual stream queries. However, streaming systems often run multiple queries concurrently, and may exploit sharing opportunities across the concurrent queries. Under such shared query execution, stream-sorting buffers can be shared across queries as well, which can potentially reduce the overall memory cost incurred by the sorting buffers. In this paper, focusing on windowed stream queries, we propose a solution for doing QDDH for concurrent queries, across which common source and stream-filtering operators are shared. Experimental results show that our solution can determine the optimal way of sharing sorting buffers across the concurrent queries, such that the goal of quality-driven result-latency minimization is achieved for each query at a minimum memory cost.