Goetz Graefe
Skip Abstract Section
Abstract
In 1987, Jim Gray and Gianfranco Putzolu published their now-famous five-minute rule for trading off memory and I/O capacity. Their calculation compares the cost of holding a record (or page) permanently in memory with the cost of performing disk I/O each time the record (or page) is accessed, using appropriate fractions of prices for RAM chips and disk drives. The name of their rule refers to the break-even interval between accesses. If a record (or page) is accessed more often, it should be kept in memory; otherwise, it should remain on disk and read when needed.
- Gray, J., Putzolu, G.R. 1987. The 5-minute rule for trading memory for disk accesses and the 10-byte rule for trading memory for CPU time. SIGMOD Record 16(3): 395-398. Google Scholar
Digital Library
- Gray, J., Graefe, G. 1997. The five-minute rule ten years later, and other computer storage rules of thumb. SIGMOD Record 26(4): 63-68. Google ScholarDigital Library
- Larus, J.R., Rajwar, R. 2007. Transactional Memory. Synthesis Lectures on Computer Architecture. Morgan and Claypool. Google ScholarDigital Library
- Hamilton, J. 2007. An architecture for modular data centers. CIDR (Conference on Innovative Data Systems Research).Google Scholar
- Gray, J., Fitzgerald, B. Flash Disk Opportunity for Server-Applications; http://research.microsoft.com/~gray/papers/FlashDiskPublic.doc.Google Scholar
- Härder, T., Reuter, A. 1983. Principles of transactionoriented database recovery. ACM Computing Surveys 15(4): 287-317. Google ScholarDigital Library
- Chen, P.M., Lee, E.L., Gibson, G.A., Katz, R.H., Patterson, D.A. 1994. RAID: High-performance, reliable secondary storage. ACM Computing Surveys 26(2): 145-185. Google ScholarDigital Library
- See reference 7.Google Scholar
- Ousterhout, J.K., Douglis, F. 1989. Beating the I/O bottleneck: A case for log-structured file systems. Operating Systems Review 23(1): 11-28. Google ScholarDigital Library
- Woodhouse, D. 2001. JFFS: the Journaling Flash File System. Ottawa Linux Symposium. Red Hat Inc.Google Scholar
- See reference 1.Google Scholar
- See reference 1.Google Scholar
- See reference 2.Google Scholar
- See reference 1.Google Scholar
- See reference 5.Google Scholar
- See reference 1.Google Scholar
- See reference 2.Google Scholar
- Graefe, G. 2007. Master-detail clustering using merged indexes. Informatik ¿ Forschung und Entwicklung 21 (3-4): 127-145.Google Scholar
- Carey, M.J., DeWitt, D.J., Richardson, J.E., Shekita, E.J. 1989. Storage management in EXODUS. Object-Oriented Concepts, Databases, and Applications: 341-369. Google ScholarDigital Library
- Stonebraker, M. 1981. Operating system support for database management. Communications of the ACM 24(7): 412-418 . Google ScholarDigital Library
- Graefe, G. 2004. Write-optimized B-trees. VLDB: 672-683. Google ScholarDigital Library
- See reference 21.Google Scholar
- See reference 2.Google Scholar
- Bayer, R., McCreight, E.M. 1970. Organization and maintenance of large ordered indexes. SIGFIDET Workshop: 107-141.Google ScholarDigital Library
- Bayer, R., Unterauer, K. 1977. Prefix B-trees. ACM Transactions on Database Systems 2(1): 11-26. Google ScholarDigital Library
- O'Neil, P.E. 1992. The SB-Tree: An index-sequential structure for high-performance sequential access. Acta Informatica 29(3): 241-265. Google ScholarDigital Library
- Lomet, D.B. 2001. The evolution of effective Btree page organization and techniques: A personal account. SIGMOD Record 30(3): 64-69. Google ScholarDigital Library
- Bender, M.A., Demaine, E.D., Farach-Colton, M. 2005. Cache-oblivious B-trees. SIAM Journal on Computing 35(2): 341-358. Google ScholarDigital Library
- Graefe, G. 2006. Implementing sorting in database systems. ACM Computing Surveys 38(3). Google ScholarDigital Library
- Nyberg, C., Barclay, T., Cvetanovic, Z., Gray, J., Lomet, D.B. 1995. AlphaSort: A cache-sensitive parallel external sort. VLDB Journal 4(4): 603-627. Google ScholarDigital Library
- Rivoire, S., Shah, M. Ranganathan, P., Kozyrakis, C. 2007. JouleSort: A balanced energy-efficiency benchmark. SIGMOD. Google ScholarDigital Library
- Shatdal, A., Kant, C., Naughton, J.F. 1994. Cacheconscious algorithms for relational query processing. VLDB: 510-521. Google ScholarDigital Library
- DeWitt, D.J., Naughton, J.F., Burger, J. 1993. Nested loops revisited. PDIS: 230-242. Google ScholarDigital Library
- Graefe, G. 2003. Executing nested queries. BTW: 58-77.Google Scholar
- See reference 24.Google Scholar
- See reference 18.Google Scholar
- Härder, T. 1978. Implementing a generalized access path structure for a relational database system. ACM Transactions on Database Systems 3(3): 285-298. Google ScholarDigital Library
Index Terms
- The Five-Minute Rule 20 Years Later: and How Flash Memory Changes the Rules: The old rule continues to evolve, while flash memory adds two new rules.
Recommendations
The five-minute rule 20 years later (and how flash memory changes the rules)
Barbara Liskov: ACM's A.M. Turing Award WinnerRevisiting Gray and Putzolu's famous rule in the age of Flash.
The five-minute rule ten years later, and other computer storage rules of thumb
Simple economic and performance arguments suggest appropriate lifetimes for main memory pages and suggest optimal page sizes. The fundamental tradeoffs are the prices and bandwidths of RAMs and disks. The analysis indicates that with today's technology, ...
The five-minute rule twenty years later, and how flash memory changes the rules
DaMoN '07: Proceedings of the 3rd international workshop on Data management on new hardwareIn 1987, Gray and Putzolo presented the five-minute rule, which was reviewed and renewed ten years later in 1997. With the advent of flash memory in the gap between traditional RAM main memory and traditional disk systems, the five-minute rule now ...
Comments