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. A. Ailamaki, D. DeWitt, M. Hill, and D. Wood. DBMSs on a modern processor: Where does time go. In VLDB 1999, pages 266-277, 1999.
2. A. Ailamaki, D. J. DeWitt, M. D. Hill, and M. Skounakis. Weaving relations for cache performance. In Proceedings of VLDB Conference, 2001.
3. P. A. Boncz, S. Manegold, and M. L. Kersten. Database architecture optimized for the new bottleneck: Memory access. In Proceedings of the 25th VLDB Conference, pages 54-65, 1999.
4. A. Cayley. On the theory of the analytical forms called trees ii. Phil. Mag., 18:374-378, 1859.
5. C. Consel and F. Noel. A general approach for run-time specialization and its application to C. In Symposium on Principles of Programming Languages, pages 145-156, 1996.
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. F. Fabret, H.-A. Jacobsen, F. LLirbat, J. Pereira, K. A. Ross, and D. Shasha. Filtering algorithms and implementation for very fast publish/subscribe. In Proceedings of the ACM SIGMOD Conference, May 2001.
9. H. Garcia-Molina and K. Salem. Main memory database systems: An overview. IEEE Transactions on Knowledge and Data Engineering, 4(6):509-516, 1992.
10. J. Gray and P. J. Shenoy. Rules of thumb in data engineering. In International Conference on Data Engineering, pages 3-12, 2000.
11. D. Heller. Rabbit: A performance counters library for intel/amd processors and linux., 2000. http://www.scl.ameslab.gov/Projects/Rabbit/.
12. J. M. Hellerstein and M. Stonebraker. Predicate migration: Optimizing queries with expensive predicates. In Proceedings of the ACM SIGMOD Conference, 1993.
13. T. J. Lehman, E. J. Shekita, and L.-F. Cabrera. An evaluation of starburst's memory resident storage component. IEEE Transactions on knowledge and data enginnering, 4(6):555-566, 1992.
14. S. Manegold, P. A. Boncz, and M. L. Kersten. What happens during a join? Dissecting CPU and memory optimization effects. In Proceedings of the VLDB Conference, pages 339-350, 2000.
15. F. Noel, L. Hornof, C. Consel, and J. L. Lawall. Automatic, template-based run-time specialization: Implementation and experimental study. In International Conference on Computer Languages, pages 132-142, 1998.
16. J. Pereira, F. Fabret, F. Llirbat, R. Preotiuc-Pietro, K. A. Ross, and D. Shasha. Publish/subscribe on the web at extreme speed. In Proceedings of the VLDB Conference, pages 627-630, 2000.
17. P. Pucheral, J.-M. Thevenin, and P. Valduriez. Efficient main memory data management using the DBGraph storage model. In International Conference on Very Large Databases, pages 683-695, 1990.
18. J. Rao and K. A. Ross. Cache conscious indexing for decision-support in main memory. In Proceedings of the 25th VLDB Conference, pages 78-89, 1999.
19. J. Rao and K. A. Ross. Making B+-trees cache conscious in main memory. In Proceedings ACM SIGMOD Conference, pages 475-486, 2000.
20. A. Shatdal, C. Kant, and J. F. Naughton. Cache conscious algorithms for relational query processing. In Proceedings of the 20th VLDB Conference, pages 510-521, 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. S. P. Vanderwiel and D. J. Lilja. Data prefetch mechanisms. ACM Computing Surveys, 32(2):174-199, 2000.
23. K.-Y. Whang and R. Krishnamurthy. Query optimization in a memory-resident domain relational calculus database system. ACM Transactions on Database Systems, 15(1):67-95, 1990.
24. H. S. Wilf. Generatingfunctionology. Academic Press, NY, 1990.
25. R. Yung. Design of the UltraSPARC instruction fetch unit. Technical Report SMLI TR-96-59, Sun Microsystems Laboratories, 1996.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Mathematics and statistics

• Information systems

  • Information retrieval

    • Information retrieval query processing