Implementation techniques for main memory database systems

ABSTRACT

With the availability of very large, relatively inexpensive main memories, it is becoming possible keep large databases resident in main memory In this paper we consider the changes necessary to permit a relational database system to take advantage of large amounts of main memory We evaluate AVL vs B+-tree access methods for main memory databases, hash-based query processing strategies vs sort-merge, and study recovery issues when most or all of the database fits in main memory As expected, B+-trees are the preferred storage mechanism unless more than 80--90% of the database fits in main memory A somewhat surprising result is that hash based query processing strategies are advantageous for large memory situations

REFERENCES

• 1: 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]
• 2: {BLAS77} Blasgen, M W and K P Eswaran, "Storage and Access in Relational Databases," IBM Systems Journal, Vol 16, No 4, 1977
• 3: {CESA82} Cesarini, F and G Soda, "Binary Trees Paging", Information Systems, Vol 7, No 4, pp 337--344, 1982
• 4: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 5: C. J. Date, An introduction to database systems: vol. I (4th ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1986
• 6: {GOOD81} Goodman, J R, "An Investigation of Multiprocessor Structures and Algorithms for Data Base Management," Electronics Research Laboratory Memorandum No UCB/ERL M81/33, University of California, Berkeley, May 1981
• 7: Jim Gray , Paul McJones , Mike Blasgen , Bruce Lindsay , Raymond Lorie , Tom Price , Franco Putzolu , Irving Traiger, The Recovery Manager of the System R Database Manager, ACM Computing Surveys (CSUR), v.13 n.2, p.223-242, June 1981 [doi>10.1145/356842.356847]
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: {KITS83} Kitsuregawa, M. et al, "Application of Hash to Data Base Machine and its Architecture", New Generation Computing, No 1, 1983, 62--74
• 10: {MUNT70} Muntz, R and R Uzgalis, "Dynamic Storage Allocation for Binary Search Trees in a Two-Level Memory," Proceedings of the Princeton Conference on Information Sciences and Systems, No 4, pp 345--349, 1970
• 11: David P. Reed, Implementing atomic actions on decentralized data, ACM Transactions on Computer Systems (TOCS), v.1 n.1, p.3-23, Feb. 1983 [doi>10.1145/357353.357355]
• 12: 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]
• 13: S. Bing Yao , David DeJong, Evaluation of database access paths, Proceedings of the 1978 ACM SIGMOD international conference on management of data, May 31-June 02, 1978, Austin, Texas [doi>10.1145/509252.509273]