ON UTILIZING ATTRIBUTE CARDINALITY MAPS TO ENHANCE QUERY OPTIMIZATION IN THE ORACLE DATABASE SYSTEM

摘要

All modern-day Database Management Systems (DBMS) use histograms in approximating query result sizes in the query optimizer. This is because histograms are simple structures, and can be easily utilized in determining efficient Query Evaluation Plans (QEPs). Recently, Oommen and Thiyagarajah introduced two new histograms methods (Thiyagarajah, 1999), namely the Rectangular Attribute Cardinality Map (R-ACM), and the Trapezoidal Attribute Cardinality Map (T-ACM). The superiority of these in yielding more accurate query result size estimates has been well demonstrated, and the resulting superior QEPs for a theoretically-modeled database was shown in (Oommen and Rueda, 2002). In this paper we make a "conceptual leap" and demonstrate how the ACMs can be incorporated into a real-life DBMS. This has been done by designing and implementing a prototype which sits on top of an ORACLE 9i system. The integration is achieved in C/C++ and PL/SQL, and serves as a prototype "plug-in" to the ORACLE system, since it is fully integrated and completely transparent to users. The superiority of utilizing the ACM histograms is rigorously validated by conducting an extensive set of experiments on the TPC-H benchmark data sets, and by testing on equi-select and equi-join queries. The entire set of experimental results obtained by integrating the underlying algorithms into the ORACLE query optimizer can be found in (Chen, 2003).