Selection conditions in main memory

Abstract

We consider the fundamental operation of applying a compound filtering condition 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 for conjunctive conditions. We also develop an efficient heuristic optimization algorithm. We also show how records can be ordered to further reduce branch misprediction effects.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. Ailamaki, A., DeWitt, D., Hill, M., and Wood, D. 1999. DBMSs on a modern processor: Where does time go. In Proceedings of the VLDB Conference. 266--277.
2. Ailamaki, A., DeWitt, D. J., Hill, M. D., and Skounakis, M. 2001. Weaving relations for cache performance. In Proceedings of the VLDB Conference. 169--180.
3. Bhat, G. S. and Savage, C. D. 1996. Balanced Gray codes. Elect. J. Combin. 3, 1, R25.
4. Boncz, P. A., Manegold, S., and Kersten, M. L. 1999. Database architecture optimized for the new bottleneck: Memory access. In Proceedings of the 25th VLDB Conference. 54--65.
5. Cayley, A. 1859. On the theory of the analytical forms called trees II. Phil. Mag. 18, 374--378.
6. Consel, C. and Noel, F. 1996. A general approach for run-time specialization and its application to C. In Proceedings of the Symposium on Principles of Programming Languages. 145--156.
7. Fabret, F., Jacobsen, H.-A., LLirbat, F., Pereira, J., Ross, K. A., and Shasha, D. 2001. Filtering algorithms and implementation for very fast publish/subscribe. In Proceedings of the ACM SIGMOD Conference. ACM, New York. 115--126.
8. Garcia-Molina, H. and Salem, K. 1992. Main memory database systems: An overview. IEEE Trans. Knowl. Data Eng. 4, 6, 509--516.
9. Gray, J. and Shenoy, P. J. 2000. Rules of thumb in data engineering. In Proceedings of the International Conference on Data Engineering. 3--12.
10. Heller, D. 2000. Rabbit: A performance counters library for intel/amd processors and linux. http://www.scl.ameslab.gov/Projects/Rabbit/.
11. Hellerstein, J. M. and Stonebraker, M. 1993. Predicate migration: Optimizing queries with expensive predicates. In Proceedings of the ACM SIGMOD Conference. ACM, New York. 267--276.
12. Intel Corp. 1999. Intel Architecture Optimization: Reference Manual.
13. Intel Corp. 2000. Intel IA-64 Architecture Software Developer's Manual, Volume 1 Rev. 1.0. Available at http://developer.intel.com/design/ia-64/manuals/.
14. Lehman, T. J., Shekita, E. J., and Cabrera, L.-F. 1992. An evaluation of starburst's memory resident storage component. IEEE Trans. Knowl. Data Eng. 4, 6, 555--566.
15. Manegold, S., Boncz, P. A., and Kersten, M. L. 2000. What happens during a join? Dissecting CPU and memory optimization effects. In Proceedings of the VLDB Conference. 339--350.
16. Noel, F., Hornof, L., Consel, C., and Lawall, J. L. 1998. Automatic, template-based run-time specialization: Implementation and experimental study. In Proceedings of the International Conference on Computer Languages. 132--142.
17. Pereira, J., Fabret, F., Llirbat, F., Preotiuc-Pietro, R., Ross, K. A., and Shasha, D. 2000. Publish/ subscribe on the web at extreme speed. In Proceedings of the VLDB Conference. 627--630.
18. Pucheral, P., Thevenin, J.-M., and Valduriez, P. 1990. Efficient main memory data management using the DBGraph storage model. In Proceedings of the International Conference on Very Large Databases. 683--695.
19. Rao, J. and Ross, K. A. 1999. Cache conscious indexing for decision-support in main memory. In Proceedings of the 25th VLDB Conference. 78--89.
20. Rao, J. and Ross, K. A. 2000. Making B+-trees cache conscious in main memory. In Proceedings ACM SIGMOD Conference. ACM, New York, 475--486.
21. Savage, C. D. 1997. A survey of combinatorial Gray codes. SIAM Review 39, 4, 605--629.
22. Shatdal, A., Kant, C., and Naughton, J. F. 1994. Cache conscious algorithms for relational query processing. In Proceedings of the 20th VLDB Conference. 510--521.
23. Sloane, N. J. A. 2000. The on-line encyclopedia of integer sequences. published electronically at http://www.research.att.com/∼njas/sequences.
24. Vanderwiel, S. P. and Lilja, D. J. 2000. Data prefetch mechanisms. ACM Comput. Surv. 32, 2, 174--199.
25. Whang, K.-Y. and Krishnamurthy, R. 1990. Query optimization in a memory-resident domain relational calculus database system. ACM Transactions on Database Systems 15, 1, 67--95.
26. Wilf, H. S. 1990. Generatingfunctionology. Academic Press, New York.
27. Yung, R. 1996. Design of the UltraSPARC instruction fetch unit. Tech. Rep. SMLI TR-96-59, Sun Microsystems Laboratories.
28. Zhou, J. and Ross, K. A. 2002. Implementing database operations using SIMD instructions. In Proceedings of the ACM SIGMOD International Conference on Management of Data. ACM, New York. 145--156.

Index Terms

• Computer systems organization

  • Architectures

• Information systems

  • Data management systems

    • Data structures

      • Data access methods

    • Database management system engines

      • Database query processing

  • Information retrieval

• Theory of computation

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)