Fast scans and joins using flash drives

ABSTRACT

As access times to main memory and disks continue to diverge, faster non-volatile storage technologies become more attractive for speeding up data analysis applications. NAND flash is one such promising substitute for disks. Flash offers faster random reads than disk, consumes less power than disk, and is cheaper than DRAM. In this paper, we investigate alternative data layouts and join algorithms suited for systems that use flash drives as the non-volatile store.

All of our techniques take advantage of the fast random reads of flash. We convert traditional sequential I/O algorithms to ones that use a mixture of sequential and random I/O to process less data in less time. Our measurements on commodity flash drives show that a column-major layout of data pages is faster than a traditional row-based layout for simple scans. We present a new join algorithm, RARE-join, designed for a column-based page layout on flash and compare it to a traditional hash join algorithm. Our analysis shows that RARE-join is superior in many practical cases: when join selectivities are small and only a few columns are projected in the join result.

REFERENCES

• 1: Daniel J. Abadi , Samuel R. Madden , Nabil Hachem, Column-stores vs. row-stores: how different are they really?, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376712]
• 2: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , Marios Skounakis, Weaving Relations for Cache Performance, Proceedings of the 27th International Conference on Very Large Data Bases, p.169-180, September 11-14, 2001
• 3: P. Boncz, M. Zukowski, and N. Nes. Monetdb/x100: Hyper-pipelining query execution. CIDR, 2005.
• 4: Goetz Graefe, The five-minute rule twenty years later, and how flash memory changes the rules, Proceedings of the 3rd international workshop on Data management on new hardware, June 15-15, 2007, Beijing, China [doi>10.1145/1363189.1363198]
• 5: G. Graefe. Sorting with flash memory. Unpublished manuscript., 2008.
• 6: Stavros Harizopoulos , Velen Liang , Daniel J. Abadi , Samuel Madden, Performance tradeoffs in read-optimized databases, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 7: Taeho Kgil , Trevor Mudge, FlashCache: a NAND flash memory file cache for low power web servers, Proceedings of the 2006 international conference on Compilers, architecture and synthesis for embedded systems, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176760.1176774]
• 8: M. Kitsuregawa, H. Tanaka, and T. Moto-Oka. Application of hash to data base machine and its architecture. New Generation Comput., 1(1):63--74, 1983.
• 9: Sang-Won Lee , Bongki Moon, Design of flash-based DBMS: an in-page logging approach, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247488]
• 10: Zhe Li , Kenneth A. Ross, Fast joins using join indices, The VLDB Journal — The International Journal on Very Large Data Bases, v.8 n.1, p.1-24, April 1999 [doi>10.1007/s007780050071]
• 11: Suzanne Rivoire , Mehul A. Shah , Parthasarathy Ranganathan , Christos Kozyrakis, JouleSort: a balanced energy-efficiency benchmark, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247522]
• 12: Suzanne Rivoire , Mehul A. Shah , Parthasarathy Ranganathan , Christos Kozyrakis , Justin Meza, Models and Metrics to Enable Energy-Efficiency Optimizations, Computer, v.40 n.12, p.39-48, December 2007 [doi>10.1109/MC.2007.436]
• 13: Samsung. Samsung Semiconductor Products. Online. http://www.samsung.com/global/business/semiconductor/products/flash/Products_NANDFlash.html.
• 14: Mike Stonebraker , Daniel J. Abadi , Adam Batkin , Xuedong Chen , Mitch Cherniack , Miguel Ferreira , Edmond Lau , Amerson Lin , Sam Madden , Elizabeth O'Neil , Pat O'Neil , Alex Rasin , Nga Tran , Stan Zdonik, C-store: a column-oriented DBMS, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 15: J. Zhou and K. A. Ross. A multi-resolution block storage model for database design. IDEAS, July 2003.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

Additional Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.1 Semiconductor Memories

General Terms:
Algorithms, Performance