Query processing in main memory database management systems

ABSTRACT

Most previous work in the area of main memory database systems has focused on the problem of developing query processing techniques that work well with a very large buffer pool. In this paper, we address query processing issues for memory resident relational databases, an environment with a very different set of costs and priorities. We present an architecture for a main memory DBMS, discussing the ways in which a memory resident database differs from a disk-based database. We then address the problem of processing relational queries in this architecture, considering alternative algorithms for selection, projection, and join operations and studying their performance. We show that a new index structure, the T Tree, works well for selection and join processing in memory resident databases. We also show that hashing methods work well for processing projections and joins, and that an old join method, sort-merge, still has a place in main memory.

REFERENCES

• AHU74: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• AHK85: A Ammann, M Hanrahan and R Knshnamurt.hy, Design of a Memory Resident DBMS, Proc IEEE COMPCON, San Francisco, February 1985
• Bab79: E. Babb, Implementing a relational database by means of specialzed hardware, ACM Transactions on Database Systems (TODS), v.4 n.1, p.1-29, March 1979 [doi>10.1145/320064.320065]
• BBD83: Dina Bitton , Haran Boral , David J. DeWitt , W. Kevin Wilkinson, Parallel algorithms for the execution of relational database operations, ACM Transactions on Database Systems (TODS), v.8 n.3, p.324-353, Sept. 1983 [doi>10.1145/319989.319991]
• BIE77: M Blasgen and K Eswaran, Storage and Access m Relational Databases, IBM Systems Journal 16,4 (1977)
• Bra84: Kjell Bratbergsengen, Hashing Methods and Relational Algebra Operations, Proceedings of the 10th International Conference on Very Large Data Bases, p.323-333, August 27-31, 1984
• Com79: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• Dat81: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• Dat85: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• DKO84: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• DeG85: D DeWltt and R Gerber, Muluproeessor Hash-Based Join Algonthms, Proc of l l th lnt Conf on Very Large Data Bases, Stockholm, Sweden, August 1985
• Eic86: M Etch, MMDB Recovery, Southern Methodist Umv Dept of Computer Sciences Teeh Rep # 86-CSE-1 I, March 1986
• EIB84: Klaus Elhardt , Rudolf Bayer, A database cache for high performance and fast restart in database systems, ACM Transactions on Database Systems (TODS), v.9 n.4, p.503-525, Dec. 1984 [doi>10.1145/1994.1995]
• FNP79: Ronald Fagin , Jurg Nievergelt , Nicholas Pippenger , H. Raymond Strong, Extendible hashing—a fast access method for dynamic files, ACM Transactions on Database Systems (TODS), v.4 n.3, p.315-344, Sept. 1979 [doi>10.1145/320083.320092]
• Fis86: M Pisbeta, Techology '86 Sohd State, IEEE Spectrum 23,1 (January 1986)
• GLV83: H Garela-Mohna, R J Lipton and J Valdes, A Massive Memory Maclune, Pnnceton Umv EECS Dept Teeh Rep # 315, July 1983
• HoT85: Susan Horwitz , Tim Teitelbaum, Relations and attributes: A symbiotic basis for editing environments, Proceedings of the ACM SIGPLAN 85 symposium on Language issues in programming environments, p.93-106, June 25-28, 1985, Seattle, Washington, United States
• IBM79: IBM, IMS Verston 1 Release 1 5 Fast Path Feature Descrzpnon and Destgn Grade, IBM World Trade Systems Centers (G320-5775), 1979
• Knu73: D Knuth, Sornng and Searching, Addison-Wesley, 1973
• LeC85: T Lehman and M Carey, A Study of Index Structures for Mare Memory Database Management Systems, UW CS Tech Rep # 605, July 1985 (A revased version has been subrrntted for pubhcauon)
• LeR85: M Leland and W Roome, The Stilton Database Machine, Proc 4th Int Workshop on Database Machines, Grand Bahama Island, March 1985
• Lin84: Mark A. Linton, Implementing relational views of programs, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.132-140, April 1984
• Lit80: W Lltwm, Linear Hastung A New Tool For File and Table Addressing, Proc of 6th Int Conf on Very Large Data Bases, Montreal, Canada, October 1980
• SAC79: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• Sha86: Leonard D. Shapiro, Join processing in database systems with large main memories, ACM Transactions on Database Systems (TODS), v.11 n.3, p.239-264, Sept. 1986 [doi>10.1145/6314.6315]
• Sno84: Richard Snodgrass, Monitoring in a software development environment: A relational approach, Proceedings of the first ACM SIGSOFT/SIGPLAN software engineering symposium on Practical software development environments, p.124-131, April 1984
• VaG84: Patrick Valduriez , Georges Gardarin, Join and Semijoin Algorithms for a Multiprocessor Database Machine, ACM Transactions on Database Systems (TODS), v.9 n.1, p.133-161, March 1984 [doi>10.1145/348.318590]
• War81: D H D Warren, Efficient Processing of Interacuve Relauonal Database Queries Expressed m Logic, Proc of 7th lnt Conf on Very Large Data Bases, Cannes, Fance, September, 1981

INDEX TERMS

Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.3 Other Architecture Styles

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management
          Subjects: Main memory

  E. Data
  E.1 DATA STRUCTURES
  E.2 DATA STORAGE REPRESENTATIONS
      Subjects: Hash-table representations

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

General Terms:
Algorithms, Design, Performance