Query Mesh: Multi-Route Query Processing Technology

Rimma V. Nehme, Karen E. Works, Elke A. Rundensteiner, Elisa Bertino

TL;DR

This paper introduces "Query Mesh" (QM), a novel approach to processing data queries that addresses the limitations of traditional single-plan optimization and overly dynamic multi-plan systems. QM computes multiple query execution routes optimized for different data subsets a priori, using a classifier to dynamically assign incoming data to the best route at runtime, offering a practical balance between optimization efficiency and adaptability.

What Problem Does This Paper Address?

In database systems, query optimization typically involves selecting a single, "best" execution plan for a query based on overall data statistics. However, real-world datasets are often heterogeneous, meaning a single plan might be highly inefficient for certain subsets of the data. For instance, network traffic data can have varying packet discard probabilities based on traffic type, or stock market data might exhibit different fluctuation patterns across various sectors.

Existing solutions either stick to a single plan (leading to suboptimal performance on diverse data) or use highly dynamic approaches like "Eddies," which continuously re-optimize for each individual data tuple. While Eddies can discover optimal routes, this constant re-optimization incurs significant overhead and can lead to larger data tuple sizes to store routing information. This paper aims to bridge this gap by proposing a system that pre-computes multiple optimized routes for distinct data subsets and uses a lightweight classifier to route data efficiently at runtime.

Methods

The core of the Query Mesh (QM) system lies in its two main components: the QM Optimizer and the QM Executor.

The QM Optimizer works offline to create a "logical QM solution." This involves:

  • Multi-Route Computation: Identifying and optimizing multiple distinct query execution routes, each tailored for a specific subset of data with unique statistical properties.
  • Classifier Induction: Building a decision tree-based classifier. This classifier learns to map incoming data characteristics to the most appropriate pre-computed route. The induction process uses machine learning measures like entropy and information gain for efficient and compact classifier construction.

The QM Executor handles the runtime execution:

  • Physical Infrastructure: It instantiates a runtime infrastructure comprising an Online Classifier Operator and a Self-Routing Fabric (SRF).
  • Online Classification: Incoming data tuples are first processed by the Online Classifier, which uses the induced decision tree to quickly assign each tuple to a specific route.
  • Self-Routing Fabric (SRF): This is the core execution engine. It uses a stack-based encoding of route instructions within data tuples (called "r-tokens"). Operators in the SRF process tuples based on these instructions, "popping" their index from the stack as they complete their task and forwarding the tuple to the next operator in the route. This decentralized approach avoids a central router and allows for efficient multi-route execution.
  • QM Adaptor: For dynamic environments, the QM system includes an adaptor that monitors for concept drift (changes in data characteristics). When drift is detected, a new QM solution (classifier and routes) is computed offline, and the online classifier is updated with minimal runtime overhead.

Datasets

The paper mentions using the Network-based Moving Objects Generator [2] to create continuously moving object data (e.g., cars, pedestrians with GPS) for their demonstration scenario. This data is used for training and evaluating the QM system.

Key Insights and Ideas

  • The "Middle Ground" is Key: QM offers a practical compromise between static, single-plan optimization and dynamic, per-tuple re-optimization. It achieves efficiency by pre-optimizing for known data variations while maintaining low runtime overhead through a lightweight classifier.
  • Decoupled Optimization and Execution: The separation of the QM Optimizer (offline) and QM Executor (runtime) is crucial. This allows for complex optimization without impacting query processing speed and enables efficient adaptation by simply updating the classifier.
  • Self-Routing Fabric (SRF) for Efficiency: The SRF's stack-based r-token encoding allows operators to directly route tuples without a central coordinator, enabling efficient parallel execution of multiple routes.
  • Lightweight Adaptivity: The QM Adaptor's ability to update the classifier with minimal overhead is a significant advantage for streaming environments where data characteristics can change over time.

Key Results

The paper focuses on demonstrating the QM framework and its components rather than presenting extensive quantitative results. The key qualitative findings and expected benefits highlighted are:

  • Improved Performance: QM is expected to offer better query execution performance compared to single-plan systems on heterogeneous data and be more efficient than Eddies due to reduced runtime overhead.
  • Efficient Adaptability: The system can adapt to changes in data characteristics with near-zero runtime overhead by updating the classifier.
  • Practicality: The demonstration scenario (Ubi-City) and the use of standard query languages (SQL with a hint) suggest the practical applicability of the QM approach.

Limitations and Future Work

  • Combinatorial Explosion: The paper acknowledges the challenge of a combinatorial explosion in the search space for finding optimal QM solutions, especially with multiple routes.
  • Dataset Selection: Selecting a good representative dataset for training the QM model is identified as a research challenge.
  • Interplay between Routes and Classifier: The dependency between the choice of execution routes and the classifier model presents a complex optimization problem.
  • Future Work: The authors suggest exploring various techniques for training data collection and their impact on the resulting QM. They also plan to illustrate different strategies for partitioning training data and computing routes. The paper also mentions demonstrating the performance benefits of QM compared to static single-plan and Eddies systems.

Summary updated

BibTeX
@article{nehme2009query,
  author = {Rimma V. Nehme and Karen E. Works and Elke A. Rundensteiner and Elisa Bertino},
  title = {{Query Mesh: Multi-Route Query Processing Technology}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  doi = {10.14778/1687553.1687583},
}
Figure