DSQoS-distributed architecture providing QoS in summary warehouses

ABSTRACT

Data warehouses (DW) that store enormous quantities of data put a major challenge in what concerns performance and scalability, as users request instant answers to their queries. Traditional solutions rely on very expensive architectures and structures for speedup and scale-up. The Summary Warehouse (SW) is an inexpensive solution that has the potential to deliver very fast approximate answers to aggregate queries using only general-purpose sampling summaries.Although summaries are expected to be extremely fast, some analysis requires larger summaries to estimate individual group results, compromising the speedup advantage. This is the accuracy/speedup (A/S) tradeoff.In this paper we propose the "Distributed Set-of-Summaries for Quality of Service" (DSQoS) that solves the A/S issue by optimizing the accuracy and response time for each query pattern in order to guarantee a desired Quality of Service (QoS). This QoS is defined in terms of response time and accuracy bounds. The strategy determines the required summary size to guarantee the accuracy targets and then dynamically select a set of summaries, distributed in various nodes, which can ensure the QoS constraints (time and accuracy). The strategy presents enormous possibilities since each node can contain summaries with different sizes, depending on the node characteristics, and can dynamically be added and removed from the system.We discuss the design of the approach and the strategies used to process queries. In the experimental section we show how the approach is able to deliver almost instant and accurate answers without employing expensive architectures, which would be impossible using other strategies.

REFERENCES

• 1: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala, Congressional samples for approximate answering of group-by queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.487-498, May 15-18, 2000, Dallas, Texas, United States
• 2: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.275-286, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: Jorge Bernardino , Pedro Furtado , Henrique Madeira, DWS-AQA: A Cost Effective Approach for Very Large Data Warehouses, Proceedings of the 2002 International Symposium on Database Engineering & Applications, p.233-242, July 17-19, 2002
• 4: Pedro Furtado , João Pedro Costa, Time-Interval Sampling for Improved Estimations in Data Warehouses, Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery, p.327-338, September 04-06, 2002
• 5: Pedro Furtado , João Pedro Costa, The BofS Solution to Limitations of Approximate Summaries, Proceedings of the Eighth International Conference on Database Systems for Advanced Applications, p.223, March 26-28, 2003
• 6: Pedro Furtado, João Pedro Costa: "Distributed Summaries: Fast Accurate Summary Warehouses" IDEAS 2003, July 2003.
• 7: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 8: P. B. Gibbons and Y. Matias. "AQUA: System and Techniques for Approximate Query Answering". Bell Labs TR 1998.
• 9: Peter J. Haas, Large-Sample and Deterministic Confidence Intervals for Online Aggregation, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.51-63, August 11-13, 1997 [doi>10.1109/SSDM.1997.621151]
• 10: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 11: TPC Benchmark H, Transaction Processing Council, June 1999. Available at http://www.tpc.org/
• 12: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 13: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Distributed databases

General Terms:
Algorithms, Design, Measurement, Performance

Keywords:
OLAP, approximate query answering, data warehouse, sampling