Conjunctive selection conditions in main memory

ABSTRACT

We consider the fundamental operation of applying a conjunction of selection conditions to a set of records. With large main memories available cheaply, systems may choose to keep the data entirely in main memory, in order to improve query and/or update performance.The design of a data-intensive algorithm in main memory needs to take into account the architectural characteristics of modern processors, just as a disk-based method needs to consider the physical characteristics of disk devices. An important architectural feature that influences the performance of main memory algorithms is the branch misprediction penalty. We demonstrate that branch misprediction has a substantial impact on the performance of an algorithm for applying selection conditions.We describe a space of "query plans" that are logically equivalent, but differ in terms of performance due to variations in their branch prediction behavior. We propose a cost model that takes branch prediction into account, and develop a query optimization algorithm that chooses a plan with optimal estimated cost. We also develop an efficient heuristic optimization algorithm.We provide experimental results for a case study based on an event notification system. Our results show the effectiveness of the proposed optimization techniques. Our results also demonstrate that significant improvements in performance can be obtained by applying a methodology that takes branch misprediction latency into account.

REFERENCES

• 1: 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
• 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: 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
• 4: A. Cayley. On the theory of the analytical forms called trees ii. Phil. Mag., 18:374-378, 1859.
• 5: Charles Consel , François Noël, A general approach for run-time specialization and its application to C, Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.145-156, January 21-24, 1996, St. Petersburg Beach, Florida, United States [doi>10.1145/237721.237767]
• 6: I. Corp. Intel Architecture Optimization: Reference Manual, February 1999.
• 7: I. Corp. Intel IA-64 Architecture Software Developer's Manual, Volume 1 Rev. 1.0, 2000. Available at http://developer.intel.com/design/ia-64/manuals/.
• 8: Françoise Fabret , H. Arno Jacobsen , François Llirbat , Joăo Pereira , Kenneth A. Ross , Dennis Shasha, Filtering algorithms and implementation for very fast publish/subscribe systems, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.115-126, May 21-24, 2001, Santa Barbara, California, United States
• 9: H. Garcia-Molina , K. Salem, Main Memory Database Systems: An Overview, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.509-516, December 1992 [doi>10.1109/69.180602]
• 10: Rules of Thumb in Data Engineering, Proceedings of the 16th International Conference on Data Engineering, p.3, February 28-March 03, 2000
• 11: D. Heller. Rabbit: A performance counters library for intel/amd processors and linux., 2000. http://www.scl.ameslab.gov/Projects/Rabbit/.
• 12: Joseph M. Hellerstein , Michael Stonebraker, Predicate migration: optimizing queries with expensive predicates, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.267-276, May 25-28, 1993, Washington, D.C., United States
• 13: T. J. Lehman , E. J. Shekita , L.-F. Cabrera, An Evaluation of Starburst's Memory Resident Storage Component, IEEE Transactions on Knowledge and Data Engineering, v.4 n.6, p.555-566, December 1992 [doi>10.1109/69.180606]
• 14: 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
• 15: Francois Noel , Luke Hornof , Charles Consel , Julia L. Lawall, Automatic, Template-Based Run-Time Specialization: Implementation and Experimental Study, Proceedings of the 1998 International Conference on Computer Languages, p.132, May 14-16, 1998
• 16: João Pereira , Françoise Fabret , François Llirbat , Radu Preotiuc-Pietro , Kenneth A. Ross , Dennis Shasha, Publish/Subscribe on the Web at Extreme Speed, Proceedings of the 26th International Conference on Very Large Data Bases, p.627-630, September 10-14, 2000
• 17: Philippe Pucheral , Jean-Marie Thévenin , P. Valduriez, Efficient main memory data management using the DBgraph storage model, Proceedings of the sixteenth international conference on Very large databases, p.683-695, September 1990, Brisbane, Australia
• 18: 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
• 19: 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
• 20: Ambuj Shatdal , Chander Kant , Jeffrey F. Naughton, Cache Conscious Algorithms for Relational Query Processing, Proceedings of the 20th International Conference on Very Large Data Bases, p.510-521, September 12-15, 1994
• 21: N. J. A. Sloane. The on-line encyclopedia of integer sequences, 2000. published electronically at http://www.research.att.com/~njas/sequences.
• 22: Steven P. Vanderwiel , David J. Lilja, Data prefetch mechanisms, ACM Computing Surveys (CSUR), v.32 n.2, p.174-199, June 2000 [doi>10.1145/358923.358939]
• 23: Kyu-Young Whang , Ravi Krishnamurthy, Query optimization in a memory-resident domain relational calculus database system, ACM Transactions on Database Systems (TODS), v.15 n.1, p.67-95, March 1990 [doi>10.1145/77643.77646]
• 24: Herbert S. Wilf, Generating functionology, Academic Press Professional, Inc., San Diego, CA, 1990
• 25: Robert Yung, Design of the UltraSPARC Instruction Fetch Unit, Sun Microsystems, Inc., Mountain View, CA, 1996

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Mathematics and statistics

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

General Terms:
Design, Theory