Asynchronous view maintenance for VLSD databases

ABSTRACT

The query models of the recent generation of very large scale distributed (VLSD) shared-nothing data storage systems, including our own PNUTS and others (e.g. BigTable, Dynamo, Cassandra, etc.) are intentionally simple, focusing on simple lookups and scans and trading query expressiveness for massive scale. Indexes and views can expand the query expressiveness of such systems by materializing more complex access paths and query results. In this paper, we examine mechanisms to implement indexes and views in a massive scale distributed database. For web applications, minimizing update latencies is critical, so we advocate deferring the work of maintaining views and indexes as much as possible. We examine the design space, and conclude that two types of view implementations, called remote view tables (RVTs) and local view tables (LVTs), provide good tradeoff between system throughput and minimizing view staleness. We describe how to construct and maintain such view tables, and how they can be used to implement indexes, group-by-aggregate views, equijoin views and selection views. We also introduce and analyze a consistency model that makes it easier for application developers to cope with the impact of deferred view maintenance. An empirical evaluation quantifies the maintenance costs of our views, and shows that they can significantly improve the cost of evaluating complex queries.

REFERENCES

• 1: CouchDB. http://couchdb.apache.org/.
• 2: D. Agrawal , A. El Abbadi , A. Singh , T. Yurek, Efficient view maintenance at data warehouses, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.417-427, May 11-15, 1997, Tucson, Arizona, United States
• 3: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 4: Michael Cafarella , Edward Chang , Andrew Fikes , Alon Halevy , Wilson Hsieh , Alberto Lerner , Jayant Madhavan , S. Muthukrishnan, Data management projects at Google, ACM SIGMOD Record, v.37 n.1, March 2008 [doi>10.1145/1374780.1374789]
• 5: Stefano Ceri , Jennifer Widom, Deriving Production Rules for Incremental View Maintenance, Proceedings of the 17th International Conference on Very Large Data Bases, p.577-589, September 03-06, 1991
• 6: Fay Chang , Jeffrey Dean , Sanjay Ghemawat , Wilson C. Hsieh , Deborah A. Wallach , Mike Burrows , Tushar Chandra , Andrew Fikes , Robert E. Gruber, Bigtable: a distributed storage system for structured data, Proceedings of the 7th USENIX Symposium on Operating Systems Design and Implementation, p.15-15, November 06-08, 2006, Seattle, WA
• 7: Songting Chen , Bin Liu , Elke A. Rundensteiner, Multiversion-based view maintenance over distributed data sources, ACM Transactions on Database Systems (TODS), v.29 n.4, p.675-709, December 2004 [doi>10.1145/1042046.1042049]
• 8: Songting Chen , Elke A. Rundensteiner, GPIVOT: Efficient Incremental Maintenance of Complex ROLAP Views, Proceedings of the 21st International Conference on Data Engineering, p.552-563, April 05-08, 2005 [doi>10.1109/ICDE.2005.71]
• 9: Latha S. Colby , Timothy Griffin , Leonid Libkin , Inderpal Singh Mumick , Howard Trickey, Algorithms for deferred view maintenance, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.469-480, June 04-06, 1996, Montreal, Quebec, Canada
• 10: Brian F. Cooper , Raghu Ramakrishnan , Utkarsh Srivastava , Adam Silberstein , Philip Bohannon , Hans-Arno Jacobsen , Nick Puz , Daniel Weaver , Ramana Yerneni, PNUTS: Yahoo!'s hosted data serving platform, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454167]
• 11: Giuseppe DeCandia , Deniz Hastorun , Madan Jampani , Gunavardhan Kakulapati , Avinash Lakshman , Alex Pilchin , Swaminathan Sivasubramanian , Peter Vosshall , Werner Vogels, Dynamo: amazon's highly available key-value store, Proceedings of twenty-first ACM SIGOPS symposium on Operating systems principles, October 14-17, 2007, Stevenson, Washington, USA
• 12: Goetz Graefe, B-tree indexes for high update rates, ACM SIGMOD Record, v.35 n.1, p.39-44, March 2006 [doi>10.1145/1121995.1122002]
• 13: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 14: Hao He , Junyi Xie , Jun Yang , Hai Yu, Asymmetric Batch Incremental View Maintenance, Proceedings of the 21st International Conference on Data Engineering, p.106-117, April 05-08, 2005 [doi>10.1109/ICDE.2005.22]
• 15: Avinash Lakshman , Prashant Malik, Cassandra: structured storage system on a P2P network, Proceedings of the 28th ACM symposium on Principles of distributed computing, August 10-12, 2009, Calgary, AB, Canada [doi>10.1145/1582716.1582722]
• 16: G. Luo, J. F. Naughton, C. J. Ellmann, and M. Watzke. A comparison of three methods for join view maintenance in parallel RDBMS. In ICDE, 2003.
• 17: C. Mohan , Inderpal Narang, Algorithms for creating indexes for very large tables without quiescing updates, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.361-370, June 02-05, 1992, San Diego, California, United States
• 18: Dallan Quass , Ashish Gupta , Inderpal Singh Mumick , Jennifer Widom, Making views self-maintainable for data warehousing, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.158-169, December 18-20, 1996, Miami Beach, Florida, United States
• 19: Dallan Quass , Jennifer Widom, On-line warehouse view maintenance, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.393-404, May 11-15, 1997, Tucson, Arizona, United States
• 20: Kenneth Salem , Kevin Beyer , Bruce Lindsay , Roberta Cochrane, How to roll a join: asynchronous incremental view maintenance, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.129-140, May 15-18, 2000, Dallas, Texas, United States
• 21: Jingren Zhou , Per-Ake Larson , Hicham G. Elmongui, Lazy maintenance of materialized views, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 22: Yue Zhuge , Héctor García-Molina , Joachim Hammer , Jennifer Widom, View maintenance in a warehousing environment, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.316-327, May 22-25, 1995, San Jose, California, United States
• 23: Yue Zhuge , Hector Garcia-Molina , Janet L. Wiener, The Strobe algorithms for multi-source warehouse consistency, Proceedings of the fourth international conference on on Parallel and distributed information systems, p.146-157, December 18-20, 1996, Miami Beach, Florida, United States

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Parallel databases

General Terms:
Performance

Keywords:
distributed and parallel databases, indexes, views