Time and space optimization for processing groups of multi-dimensional scientific queries

ABSTRACT

Data analysis applications in areas as diverse as remote sensing and telepathology require operating on and processing very large datasets. For such applications to execute efficiently, careful attention must be paid to the storage, retrieval, and manipulation of the datasets. This paper addresses the optimizations performed by a high performance database system that processes groups of data analysis requests for these applications, which we call queries. The system performs end-to-end processing of the requests, formulated as PostgreSQL declarative queries. The queries are converted into imperative descriptions, multiple imperative descriptions are merged into a single execution plan, the plan is optimized to decrease execution time via common compiler optimization techniques, and, finally, the plan is optimized to decrease memory consumption. The last two steps are experimentally shown to effectively reduc the amount of time required while conserving memory space as a group of queries is processed by the database.

REFERENCES

• 1: H. Andrade, S. Aryangat, T. Kurc, J. Saltz, and A. Sussman. Efficient execution of multi-query data analysis batches using compiler optimization strategies. In Proceedings of the 16th International Workshop on Languages and Compilers for Parallel Computing (LCPC 2003), College Station, TX, October 2003.
• 2: Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Efficient execution of multiple query workloads in data analysis applications, Proceedings of the 2001 ACM/IEEE conference on Supercomputing (CDROM), p.53-53, November 10-16, 2001, Denver, Colorado [doi>10.1145/582034.582087]
• 3: Henrique Andrade , Tahsin Kurc , Alan Sussman , Joel Saltz, Exploiting Functional Decomposition for Efficient Parallel Processing of Multiple Data Analysis Queries, Proceedings of the 17th International Symposium on Parallel and Distributed Processing, p.81.1, April 22-26, 2003
• 4: S. Aryangat. Optimizing the execution of data analysis queries. Master's thesis, Department of Computer Science, University of Maryland, December 2003.
• 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: Upen S. Chakravarthy , Jack Minker, Multiple Query Processing in Deductive Databases using Query Graphs, Proceedings of the 12th International Conference on Very Large Data Bases, p.384-391, August 25-28, 1986
• 7: Chialin Chang , Joel Saltz, Parallel aggregation on multi-dimensional scientific datasets, 2001
• 8: Chialin Chang , Bongki Moon , Anurag Acharya , Carter Shock , Alan Sussman , Joel H. Saltz, Titan: A High-Performance Remote Sensing Database, Proceedings of the Thirteenth International Conference on Data Engineering, p.375-384, April 07-11, 1997
• 9: Fa-Chung Fred Chen , Margaret H. Dunham, Common Subexpression Processing in Multiple-Query Processing, IEEE Transactions on Knowledge and Data Engineering, v.10 n.3, p.493-499, May 1998 [doi>10.1109/69.687980]
• 10: J. M. Cheng , N. M. Mattos , D. D. Chamberlin , L. G. DeMichiel, Extending relational database technology for new applications, IBM Systems Journal, v.33 n.2, p.264-279, April 1994
• 11: Renato Antonio Celso Ferreira , Joel Saltz, Compiler techniques for data parallel applications using very large multi-dimensional datasets, 2001
• 12: Renato Ferreira , Gagan Agrawal , Ruoming Jin , Joel H. Saltz, Compiling Data Intensive Applications with Spatial Coordinates, Proceedings of the 13th International Workshop on Languages and Compilers for Parallel Computing-Revised Papers, p.339-354, August 10-12, 2000
• 13: Renato Ferreira , Gagan Agrawal , Joel Saltz, Compiling object-oriented data intensive applications, Proceedings of the 14th international conference on Supercomputing, p.11-21, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335233]
• 14: Renato Ferreira , Joel H. Saltz , Gagan Agrawal, Compiler and Runtime Analysis for Efficient Communication in Data Intensive Applications, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.231-242, September 08-12, 2001
• 15: High Performance Fortran Forum. High Performance Fortran -- language specification -- version 2.0. Technical report, Rice University, January 1997. Available at http://www.netlib.org/hpf.
• 16: S. Kalluri, Z. Zhang, J. JáJá, D. Bader, N. E. Saleous, E. Vermote, and J. R. G. Townshend. A hierarchical data archiving and processing system to generate custom tailored products from AVHRR data. In 1999 IEEE International Geoscience and Remote Sensing Symposium, pages 2374--2376, 1999.
• 17: Myong H. Kang , Henry G. Dietz , Bharat Bhargava, Multiple-query optimization at algorithm-level, Data & Knowledge Engineering, v.14 n.1, p.57-75, Nov. 1994 [doi>10.1016/0169-023X(94)90009-4]
• 18: Manish Mehta , Valery Soloviev , David J. DeWitt, Batch Scheduling in Parallel Database Systems, Proceedings of the Ninth International Conference on Data Engineering, p.400-410, April 19-23, 1993
• 19: Daniel A. Menasce , Virgilio A.F. Almeida , Larry W. Dowdy, Capacity Planning and Performance Modeling: From Mainframes to Client-Server Systems, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 20: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 21: National Oceanic and Atmospheric Administration. NOAA Polar Orbiter User's Guide -- November 1998 Revision. compiled and edited by Katherine B. Kidwell. Available at http://www2.ncdc.noaa.gov/docs/podug/cover.htm.
• 22: PostgreSQL 7.3.2 Developer's Guide. http://www.postgresql.org.
• 23: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 24: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 25: M. Stonebraker. The SEQUOIA 2000 project. Data Engineering, 16(1):24--28, 1993.
• 26: Kian-Lee Tan , Hongjun Lu, Workload scheduling for multiple query processing, Information Processing Letters, v.55 n.5, p.251-257, Sept. 15, 1995 [doi>10.1016/0020-0190(95)00088-T]

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Compilers; Optimization

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

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Earth and atmospheric sciences

General Terms:
Algorithms, Performance

Keywords:
multi-query optimization, scientific databases