The Five-minute Rule
20 Years Later
and How Flash Memory Changes the Rules
5. Gray, J., Fitzgerald, B. Flash Disk Opportunity for
Server-Applications; http://research.microsoft.
com/~gray/papers/ FlashDiskPublic.doc.
6. Härder, T., Reuter, A. 1983. Principles of transaction-oriented database recovery. ACM Computing Surveys
15( 4): 287-317.
7. 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.
8. See reference 7.
9. 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.
10. Woodhouse, D. 2001. JFFS: the Journaling Flash File
System. Ottawa Linux Symposium. Red Hat Inc.
11. See reference 1.
12. See reference 1.
13. See reference 2.
14. See reference 1.
15. See reference 5.
16. See reference 1.
17. See reference 2.
18. Graefe, G. 2007. Master-detail clustering using merged
indexes. Informatik – Forschung und Entwicklung 21
( 3-4): 127-145.
19. Carey, M.J., De Witt, D.J., Richardson, J.E., Shekita, E.J.
1989. Storage management in EXODUS.
Object-Oriented Concepts, Databases, and Applications: 341-369.
20. Stonebraker, M. 1981. Operating system support for
database management. Communications of the ACM
24( 7): 412-418 .
21. Graefe, G. 2004. Write-optimized B-trees. VLDB: 672-
683.
22. See reference 21.
23. See reference 2.
24. Bayer, R., McCreight, E.M. 1970. Organization and
maintenance of large ordered indexes. SIGFIDET
Workshop: 107-141.
25. Bayer, R., Unterauer, K. 1977. Prefix B-trees. ACM
Transactions on Database Systems 2( 1): 11-26.
structure for high-performance sequential access. Acta
Informatica 29( 3): 241-265.
27. Lomet, D.B. 2001. The evolution of effective B-tree page organization and techniques: A personal
account. SIGMOD Record 30( 3): 64-69.
28. Bender, M.A., Demaine, E.D., Farach-Colton, M. 2005.
Cache-oblivious B-trees. SIAM Journal on Computing
35( 2): 341-358.
29. Graefe, G. 2006. Implementing sorting in database
systems. ACM Computing Surveys 38( 3).
30. 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.
31. Rivoire, S., Shah, M. Ranganathan, P., Kozyrakis, C.
2007. JouleSort: A balanced energy-efficiency benchmark. SIGMOD.
32. Shatdal, A., Kant, C., Naughton, J.F. 1994. Cache-conscious algorithms for relational query processing.
VLDB: 510-521.
33. De Witt, D.J., Naughton, J.F., Burger, J. 1993. Nested
loops revisited. PDIS: 230-242.
34. Graefe, G. 2003. Executing nested queries.
BTW: 58-77.
35. See reference 24.
36. See reference 18.
37. Härder, T. 1978. Implementing a generalized access
path structure for a relational database system. ACM
Transactions on Database Systems 3( 3): 285-298.
LOVE IT, HATE IT? LET US KNOW
feedback@acmqueue.com or www.acmqueue.com/forums
GOETZ GRAEFE ( Goetz.Graefe@HP.com) joined Hewlett-Packard Laboratories after seven years as an academic
researcher and teacher followed by 12 years as a product
architect and developer at Microsoft, and was recently
named an HP Fellow. Within the field of database management, his work bridges compile-time query optimization,
runtime query execution, and indexing technologies. His Volcano research project was awarded the 10-year Test-of-Time
Award at ACM SIGMOD 2000 for work on query execution,
and he received the inaugural Influential Paper Award at the
IEEE International Conference on Data Engineering in 2005
for his work on query optimization.
© 2008 ACM 1542-7730/08/0700 $5.00
This article was originally published in Proceedings of the
Third International Workshop on Data Management on
New Hardware (DaMoN 2007), June 15, 2007, Beijing,
China.
