Multiple range query optimization with distributed cache indexing

ABSTRACT

MQO is a distributed multiple query processing middleware that can use resources available on the Grid to optimize query processing for data analysis and visualization applications. It does so by introducing one or more proxies that act as front-ends to a collection of backend servers. The basic idea behind this architecture is active semantic caching, whereby queries can leverage available cached results in the proxy either directly or through transformations. While this approach has been shown to speed up query evaluation under multi-client workloads, the caching infrastructure in the backend servers is not used well for query processing. Because this collective caching infrastructure scales with the number of servers, it is an important asset. In this paper, we describe a distributed multidimensional indexing scheme that enables the proxy to directly consider the cache contents available at the backend servers for query planning and scheduling. This approach is shown to produce better query plans and faster query response times as we experimentally demonstrate.

REFERENCES

• 1: Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Active Proxy-G: optimizing the query execution process in the grid, Proceedings of the 2002 ACM/IEEE conference on Supercomputing, p.1-15, November 16, 2002, Baltimore, Maryland
• 2: Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Optimizing the Execution of Multiple Data Analysis Queries on Parallel and Distributed Environments, IEEE Transactions on Parallel and Distributed Systems, v.15 n.6, p.520-532, June 2004 [doi>10.1109/TPDS.2004.11]
• 3: Bellman, R. E. 1961. Adaptive Control Processes: A GuidedTour. Princeton University Press, NJ.
• 4: Michael D. Beynon , Tahsin Kurc , Umit Catalyurek , Chialin Chang , Alan Sussman , Joel Saltz, Distributed processing of very large datasets with DataCutter, Parallel Computing, v.27 n.11, p.1457-1478, October 2001 [doi>10.1016/S0167-8191(01)00099-0]
• 5: Michael Beynon , Chialin Chang , Umit Catalyurek , Tahsin Kurc , Alan Sussman , Henrique Andrade , Renato Ferreira , Joel Saltz, Processing large-scale multi-dimensional data in parallel and distributed environments, Parallel Computing, v.28 n.5, p.827-859, May 2002 [doi>10.1016/S0167-8191(02)00097-2]
• 6: Eugene Borovikov , Alan Sussman, A high performance multi-perspective vision studio, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782862]
• 7: Shaul Dar , Michael J. Franklin , Björn Þór Jónsson , Divesh Srivastava , Michael Tan, Semantic Data Caching and Replacement, Proceedings of the 22th International Conference on Very Large Data Bases, p.330-341, September 03-06, 1996
• 8: Parke Godfrey , Jarek Gryz, Answering Queries by Semantic Caches, Proceedings of the 10th International Conference on Database and Expert Systems Applications, p.485-498, August 30-September 03, 1999
• 9: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 10: Ibrahim Kamel , Christos Faloutsos, Parallel R-trees, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.195-204, June 02-05, 1992, San Diego, California, United States
• 11: Jik-Soo Kim , Henrique Andrade , Alan Sussman, Comparing the Performance of High-Level Middleware Systems in Shared and Distributed Memory Parallel Environments, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.30, April 04-08, 2005 [doi>10.1109/IPDPS.2005.144]
• 12: Nick Koudas , Christos Faloutsos , Ibrahim Kamel, Declustering Spatial Databases on a Multi-Computer Architecture, Proceedings of the 5th International Conference on Extending Database Technology: Advances in Database Technology, p.592-614, March 25-29, 1996
• 13: Anirban Mondal , Masaru Kitsuregawa , Beng Chin Ooi , Kian Lee Tan, R-tree-based data migration and self-tuning strategies in shared-nothing spatial databases, Proceedings of the 9th ACM international symposium on Advances in geographic information systems, November 09-10, 2001, Atlanta, Georgia, USA [doi>10.1145/512161.512169]
• 14: A Comparative Study of Spatial Indexing Techniques for Multidimensional Scientific Datasets, Proceedings of the 16th International Conference on Scientific and Statistical Database Management (SSDBM'04), p.171, June 21-23, 2004 [doi>10.1109/SSDBM.2004.1]
• 15: B. Nam , A. Sussman, Spatial indexing of distributed multidimensional datasets, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.743-750, May 09-12, 2005
• 16: Nam, B., and Sussman, A. 2006. DiST: Fully decentralized indexing for querying distributed multidimensional datasets. In Proceedings of 20th IEEE International Parallel and Distributed Processing Symposium (IPDPS).
• 17: Manuel Rodríguez-Martínez , Nick Roussopoulos, MOCHA: a self-extensible database middleware system for distributed data sources, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.213-224, May 15-18, 2000, Dallas, Texas, United States
• 18: Bernd Schnitzer , Scott T. Leutenegger, Master-Client R-Trees: A New Parallel R-Tree Architecture, Proceedings of the 11th International Conference on Scientific on Scientific and Statistical Database Management, p.68, July 28-30, 1999 [doi>10.1109/SSDM.1999.787622]
• 19: T. Sellis , S. Ghosh, On the Multiple-Query Optimization Problem, IEEE Transactions on Knowledge and Data Engineering, v.2 n.2, p.262-266, June 1990 [doi>10.1109/69.54724]
• 20: Wessels, D., and Claffy, K. C. 1998. ICP and the Squid web cache. IEEE Journal on Selected Areas in Communications 16, 3 (Apr.), 345--357.
• 21: K. Zhang , H. Andrade , L. Raschid , A. Sussman, Query planning for the grid: adapting to dynamic resource availability, Proceedings of the Fifth IEEE International Symposium on Cluster Computing and the Grid (CCGrid'05) - Volume 2, p.751-758, May 09-12, 2005

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.0 General

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness); Distributed systems

General Terms:
Algorithms, Design, Management, Performance