Implementing database operations using SIMD instructions

ABSTRACT

Modern CPUs have instructions that allow basic operations to be performed on several data elements in parallel. These instructions are called SIMD instructions, since they apply a single instruction to multiple data elements. SIMD technology was initially built into commodity processors in order to accelerate the performance of multimedia applications. SIMD instructions provide new opportunities for database engine design and implementation. We study various kinds of operations in a database context, and show how the inner loop of the operations can be accelerated using SIMD instructions. The use of SIMD instructions has two immediate performance benefits: It allows a degree of parallelism, so that many operands can be processed at once. It also often leads to the elimination of conditional branch instructions, reducing branch mispredictions.We consider the most important database operations, including sequential scans, aggregation, index operations, and joins. We present techniques for implementing these using SIMD instructions. We show that there are significant benefits in redesigning traditional query processing algorithms so that they can make better use of SIMD technology. Our study shows that using a SIMD parallelism of four, the CPU time for the new algorithms is from 10% to more than four times less than for the traditional algorithms. Superlinear speedups are obtained as a result of the elimination of branch misprediction effects.

REFERENCES

• 1: http://lava.cs.virginia.edu/bpred.html.
• 2: Sybase IQ. http://www.sybase.com/products/archivedproducts/sybaseiq.
• 3: 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
• 4: Anastassia Ailamaki , David J. DeWitt , Mark D. Hill , David A. Wood, DBMSs on a Modern Processor: Where Does Time Go?, Proceedings of the 25th International Conference on Very Large Data Bases, p.266-277, September 07-10, 1999
• 5: Peter A. Boncz , Stefan Manegold , Martin L. Kersten, Database Architecture Optimized for the New Bottleneck: Memory Access, Proceedings of the 25th International Conference on Very Large Data Bases, p.54-65, September 07-10, 1999
• 6: Shimin Chen , Phillip B. Gibbons , Todd C. Mowry, Improving index performance through prefetching, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.235-246, May 21-24, 2001, Santa Barbara, California, United States
• 7: Douglas Comer, Ubiquitous B-Tree, ACM Computing Surveys (CSUR), v.11 n.2, p.121-137, June 1979 [doi>10.1145/356770.356776]
• 8: David J. DeWitt , Jeffrey F. Naughton , Donovan A. Schneider, An Evaluation of Non-Equijoin Algorithms, Proceedings of the 17th International Conference on Very Large Data Bases, p.443-452, September 03-06, 1991
• 9: Martin Dietzfelbinger , Torben Hagerup , Jyrki Katajainen , Martti Penttonen, A reliable randomized algorithm for the closest-pair problem, Journal of Algorithms, v.25 n.1, p.19-51, Oct. 1997 [doi>10.1006/jagm.1997.0873 ]
• 10: R. Finkel and J. Bentley. Quad trees: A data structure for retrieval on composite keys. Acta Informatica, 4:1-9, 1974.
• 11: Goetz Graefe , Per-Åke Larson, B-Tree Indexes and CPU Caches, Proceedings of the 17th International Conference on Data Engineering, p.349-358, April 02-06, 2001
• 12: Antonin Guttman, R-trees: a dynamic index structure for spatial searching, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 13: InfoCharger Engine. Optimization for decision support solutions. 1998. (available from http://www.tandem.com/prod_des/ifchegpd/ifchegpd.htm).
• 14: Intel Inc. Intel architecture software developer's manual. 2001.
• 15: Intel Inc. Intel C++ compiler user's manual. 2001.
• 16: Intel Inc. Intel IA64 architecture software developer's manual. 2001.
• 17: Kihong Kim , Sang K. Cha , Keunjoo Kwon, Optimizing multidimensional index trees for main memory access, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.139-150, May 21-24, 2001, Santa Barbara, California, United States
• 18: Stefan Manegold , Peter A. Boncz , Martin L. Kersten, What Happens During a Join? Dissecting CPU and Memory Optimization Effects, Proceedings of the 26th International Conference on Very Large Data Bases, p.339-350, September 10-14, 2000
• 19: Patrick O'Neil , Dallan Quass, Improved query performance with variant indexes, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.38-49, May 11-15, 1997, Tucson, Arizona, United States
• 20: John L. Hennessy , David A. Patterson, Computer architecture (2nd ed.): a quantitative approach, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1996
• 21: Jun Rao , Kenneth A. Ross, Cache Conscious Indexing for Decision-Support in Main Memory, Proceedings of the 25th International Conference on Very Large Data Bases, p.78-89, September 07-10, 1999
• 22: Jun Rao , Kenneth A. Ross, Making B+- trees cache conscious in main memory, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.475-486, May 15-18, 2000, Dallas, Texas, United States
• 23: John T. Robinson, The K-D-B-tree: a search structure for large multidimensional dynamic indexes, Proceedings of the 1981 ACM SIGMOD international conference on Management of data, April 29-May 01, 1981, Ann Arbor, Michigan [doi>10.1145/582318.582321]
• 24: Kenneth A. Ross, Conjunctive selection conditions in main memory, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543628]
• 25: Nathan T. Slingerland , Alan J Smith, Multimedia Instruction Sets for General Purpose Microprocessors: a, University of California at Berkeley, Berkeley, CA, 2000
• 26: H. R. Strong , G. Markowsky , A. K. Chandra, Search within a Page, Journal of the ACM (JACM), v.26 n.3, p.457-482, july 1979 [doi>10.1145/322139.322146]
• 27: SUN Microsystem Inc. VIS instruction set user's manual. 2000.
• 28: Times Ten Performance Software Inc. TimesTen 4.3 and Front-Tier 2.3 product descriptions, 2002. Available at http://www.timesten.com.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Parallel databases

Additional Classification:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Parallel circuits

General Terms:
Algorithms, Documentation, Theory