Query processing techniques for solid state drives

ABSTRACT

Solid state drives perform random reads more than 100x faster than traditional magnetic hard disks, while offering comparable sequential read and write bandwidth. Because of their potential to speed up applications, as well as their reduced power consumption, these new drives are expected to gradually replace hard disks as the primary permanent storage media in large data centers. However, although they may benefit applications that stress random reads immediately, they may not improve database applications, especially those running long data analysis queries. Database query processing engines have been designed around the speed mismatch between random and sequential I/O on hard disks and their algorithms currently emphasize sequential accesses for disk-resident data.

In this paper, we investigate data structures and algorithms that leverage fast random reads to speed up selection, projection, and join operations in relational query processing. We first demonstrate how a column-based layout within each page reduces the amount of data read during selections and projections. We then introduce FlashJoin, a general pipelined join algorithm that minimizes accesses to base and intermediate relational data. FlashJoin's binary join kernel accesses only the join attributes, producing partial results in the form of a join index. Subsequently, its fetch kernel retrieves the attributes for later nodes in the query plan as they are needed. FlashJoin significantly reduces memory and I/O requirements for each join in the query. We implemented these techniques inside Postgres and experimented with an enterprise SSD drive. Our techniques improved query runtimes by up to 6x for queries ranging from simple relational scans and joins to full TPC-H queries.

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: ]]D. J. Abadi, D. S. Myers, D. J. DeWitt, and S. Madden. Materialization strategies in a column-oriented DBMS. ICDE, pages 466--475, 2007.
• 3: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill, Data page layouts for relational databases on deep memory hierarchies, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.3, p.198-215, November 2002 [doi>10.1007/s00778-002-0074-9]
• 4: ]]P. A. Boncz, M. Zukowski, and N. Nes. MonetDB/X100: Hyper--pipelining query execution. CIDR, pages 225--237, 2005.
• 5: ]]L. Bouganim, B. Jonsson, and P. Bonnet. uFlip: Understanding flash IO patterns. CIDR, 2009.
• 6: George P. Copeland , Setrag N. Khoshafian, A decomposition storage model, ACM SIGMOD Record, v.14 n.4, p.268-279, May 1985
• 7: David J DeWitt , Randy H Katz , Frank Olken , Leonard D Shapiro , Michael R Stonebraker , David Wood, Implementation techniques for main memory database systems, ACM SIGMOD Record, v.14 n.2, June 1984
• 8: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 9: ]]G. Graefe. The five-minute rule twenty years later, and how flash memory changes the rules. ACM Queue, pages 1--9, 2007.
• 10: 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
• 11: ]]S. Harizopoulos, M. A. Shah, J. Meza, and P. Ranganathan. Energy Efficiency: The New Holy Grail of Data Management Systems Research. CIDR, 2009.
• 12: Allison L. Holloway , David J. DeWitt, Read-optimized databases, in depth, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453912]
• 13: ]]J. Janukowicz, D. Reinsel, and J. Rydning. Worldwide solid state drive 2008--2012 forecast and analysis. Technical Report 212736, IDC, June 2008.
• 14: Ioannis Koltsidas , Stratis D. Viglas, Flashing up the storage layer, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453913]
• 15: 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]
• 16: Sang-Won Lee , Bongki Moon , Chanik Park , Jae-Myung Kim , Sang-Woo Kim, A case for flash memory ssd in enterprise database applications, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376723]
• 17: Yinan Li , Bingsheng He , Qiong Luo , Ke Yi, Tree Indexing on Flash Disks, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.1303-1306, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.226]
• 18: 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]
• 19: Robert Marek , Erhard Rahm, TID hash joins, Proceedings of the third international conference on Information and knowledge management, p.42-49, November 29-December 02, 1994, Gaithersburg, Maryland, United States [doi>10.1145/191246.191258]
• 20: ]]D. Myers. On the use of NAND flash memory in high-performance relational databases. MIT Msc Thesis, 2008.
• 21: Suman Nath , Phillip B. Gibbons, Online maintenance of very large random samples on flash storage, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453961]
• 22: ]]M. Polte and J. Simsa and G. Gibson. Enabling enterprise solid state disks performance. Workshop on Integrating Solid-state Memory into the Storage Hierarchy, 2009.
• 23: Kenneth A. Ross, Modeling the performance of algorithms on flash memory devices, Proceedings of the 4th international workshop on Data management on new hardware, June 13-13, 2008, Vancouver, Canada [doi>10.1145/1457150.1457153]
• 24: Mehul A. Shah , Stavros Harizopoulos , Janet L. Wiener , Goetz Graefe, Fast scans and joins using flash drives, Proceedings of the 4th international workshop on Data management on new hardware, June 13-13, 2008, Vancouver, Canada [doi>10.1145/1457150.1457154]
• 25: 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]
• 26: Konrad Stocker , Donald Kossmann , Reinhard Braumandl , Alfons Kemper, Integrating Semi-Join-Reducers into State of the Art Query Processors, Proceedings of the 17th International Conference on Data Engineering, p.575-584, April 02-06, 2001
• 27: 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

INDEX TERMS

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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

General Terms:
Algorithms, Design, Performance

Keywords:
columnar storage, flash memory, join index, late materialization, semi-join reduction, ssd