Optimizing adaptive multi-route query processing via time-partitioned indices

摘要

Adaptive multi-route query processing (AMR) is an emerging paradigm for processing stream queries in highly fluctuating environments. The content of stream data can be unpredictable. Thus, instead of selecting a fixed plan, AMR dynamically routes batches of tuples to operators in the query network based on up-to-date system statistics. The workload of query access patterns in AMR systems is ever changing. Selecting a single best index may not efficiently support all query access patterns at all times. While maintaining multiple indices to match a variety of query access patterns increases overhead and decreases throughput. Index design, while paramount for efficient query execution, is particularly challenging in AMR systems as the indices must serve the continuously evolving query access patterns. Our proposed Adaptive Multi-Route Index (AMRI) employs a bitmap time-partitioned design that serves a diverse ever changing workload of query access patterns and remains lightweight in terms of maintenance and storage requirements. We propose a high quality yet efficient assessment method modeled after hierarchical heavy hitters that exploits route relationships by modeling the frequency of the search access patterns used as nodes in a lattice. We also design assessment scheduling methods for AMRI based upon detecting changes in the search access patterns used. Our AMRI incorporates migration strategies that seek to meet the needs of both old partially serviced and new incoming search requests. Our experimental study using both synthetic and real data streams demonstrates that AMRI strikes a balance between effectively supporting dynamic stream environments while keeping the index overhead to a minimum. Using an environmental data set collected in the Intel Berkeley Research lab, our AMRI produced on average 68% more cumulative throughput than the state-of-the-art approach.