Distributed Online Aggregation

Sai Wu, Shouxu Jiang, Beng Chin Ooi, Kian-Lee Tan

TL;DR

This paper introduces Distributed Online Aggregation (DoA), a novel system that brings the benefits of "online aggregation" (providing progressively refined approximate answers to complex queries) to distributed environments. DoA leverages a Distributed Hash Table (DHT) for efficient data distribution and management, enabling faster query responses and reduced computational overhead compared to traditional approaches.

What Problem Does This Paper Address?

In today's data-rich enterprise environments, decision-makers often need to query large, distributed datasets. Traditional methods like consolidating data into a central data warehouse are costly and lack scalability. While distributed systems like MapReduce offer parallelism, they often require significant waiting time for results. Furthermore, aggregate queries, which summarize vast amounts of data, are computationally expensive and time-consuming. The core problem this paper addresses is how to efficiently provide fast, progressively refined approximate answers to aggregate queries in a distributed setting, where data is spread across multiple autonomous sites. This is crucial for applications where immediate feedback and timely insights are more valuable than a perfectly precise, but delayed, answer.

Methods

The paper proposes Distributed Online Aggregation (DoA), which extends the concept of online aggregation to a distributed context using a DHT overlay (specifically Chord). Here's a breakdown of their key methods:

  • Iterative Sampling and Aggregation: DoA works by iteratively retrieving small sets of random samples from data sites. These samples are then distributed to processing sites, where local aggregates are computed. A coordinator site then combines these local aggregates into a global approximate answer. This process refines the answer and its confidence interval with each iteration.
  • DHT-based Distribution: Data and processing nodes are organized in a DHT network. This provides a structured overlay for efficient data discovery and routing.
  • Linear Hashing for Dynamic Load Balancing: To adapt to varying sample sizes and query workloads, DoA employs linear hashing. This technique dynamically adjusts the number of processing nodes (buckets) as the sample size grows, ensuring efficient parallelism.
  • Synopsis Maintenance: To reduce sampling overhead for future queries, DoA retains processed samples as a precomputed "synopsis" in the network. This synopsis is incrementally maintained to reflect data updates, balancing storage costs with query performance.
  • Adaptive Sampling: The system uses a self-adaptive sampling scheme to ensure unbiased samples, even when data distribution estimates are approximate.
  • Joining Group Namespace: For multi-relational queries (joins), a novel namespace based on "joining groups" is introduced to ensure that related tuples from different tables are consistently routed to the same processing nodes.

Datasets

The experiments were conducted on PlanetLab, a global research network. The TPC-H toolkit was used to generate test data. Specifically, the lineitem and orders tables from the TPC-H benchmark were used, with datasets of 1GB and 5GB generated to simulate multi-corporate scenarios.

Key Insights and Ideas

  • Online Aggregation in the Wild: The paper successfully demonstrates that the benefits of online aggregation (interactive query refinement, early feedback) can be effectively extended to distributed, P2P-like environments.
  • DHT + Linear Hashing Synergy: The combination of a structured DHT for organization and linear hashing for dynamic load balancing is a powerful approach for managing distributed processing resources in response to varying data volumes.
  • Synopsis as a Performance Booster: Maintaining precomputed samples (synopsis) significantly reduces the sampling overhead for subsequent queries, leading to substantial performance gains, especially for repeated queries or larger datasets.
  • Adaptive Sampling is Crucial: In a distributed setting where exact data distribution is unknown or dynamic, adaptive sampling techniques are essential for obtaining unbiased results.
  • Joining Groups for Efficient Joins: The concept of "joining groups" provides a practical way to define consistent namespaces for join operations in a distributed environment, ensuring correct query processing.

Key Results

  • Reduced Initial Waiting Time: DoA significantly reduces the initial waiting time for approximate answers compared to traditional methods.
  • Scalability with Data Size: AQP with synopsis demonstrated better scalability for larger datasets compared to AQP without synopsis and CQP (Complete Query Processing).
  • Accuracy vs. Performance Trade-off: The experiments showed a clear trade-off between error bound/confidence and processing time, with smaller error bounds and higher confidence requiring more samples and thus longer processing times.
  • Accurate Error Estimation: The system's estimated error bounds were found to be quite accurate, with real error rates strictly bounded by the estimated ones.
  • Effective Load Balancing: The use of DHT protocols effectively balanced the query load across the network nodes.

Limitations and Future Work

  • Schema Mapping Complexity: The paper assumes that data nodes have already built mapping relations to a global schema, acknowledging that schema mapping itself is a complex problem beyond the scope of this work.
  • Batch Updates: The synopsis maintenance strategy assumes batch updates to local databases, which might not be suitable for highly dynamic, real-time transactional systems.
  • Coordinator Overload: While addressed by potentially starting up more coordinators, the paper notes that a large number of groups generated by processing nodes could still overload the coordinator.
  • Future Work: The authors suggest exploring more sophisticated index schemes for optimizing query processing and further investigating gossip-based methods for parameter estimation in real systems. They also highlight the potential for extending their work to other DHT overlays.

Summary updated

BibTeX
@article{wu2009distributed,
  author = {Sai Wu and Shouxu Jiang and Beng Chin Ooi and Kian-Lee Tan},
  title = {{Distributed Online Aggregation}},
  journal = {Proc. VLDB Endow.},
  year = {2009},
  url = {https://openreview.net/forum?id=6vd7h9bZEqf},
}
Figure