On Enhancing Query Optimization in the Oracle Database System by Utilizing Attribute Cardinality Maps

Central to the process of query optimization in all real-life modern-day Database Management Systems (DBMS) is the use of histograms. These have been used for decades in approximating query result sizes in the query optimizer, and methods such as the Equi

  • PDF / 995,670 Bytes
  • 34 Pages / 430 x 660 pts Page_size
  • 102 Downloads / 255 Views

DOWNLOAD

REPORT


oduction In this paper, we1 we consider the well-known problem of query optimization2, and propose how we can incorporate some recently-proposed histogram-based methods to enhance a fully-developed real-life database system. 1

2

The first author also holds an Adjunct Professorship with the Department of Information and Communication Technology, Agder University College, Grooseveien 36, N-4876 Grimstad, Norway. A brief, preliminary version of this paper was presented at ICEIS-2006, the 2006 International Conference on Enterprise Information Systems, in Cyprus, in May 2006. This talk was a Plenary/Keynote Talk of the Conference.

Y. Manolopoulos et al. (Eds.): ICEIS 2006, LNBIP 3, pp. 38–71, 2008. c Springer-Verlag Berlin Heidelberg 2008 

On Enhancing Query Optimization in the Oracle Database System by Utilizing ACMs

39

Query optimization can usually be achieved in two different ways: on the database server side, and on the application side. The former method depends on the architecture and design of the core of the DBMS, while the latter depends largely on the applications themselves. The design of the database query optimizer, and the algorithms it utilizes, plays an important role in the efficiency of the DBMS. As in the case of various algorithms used in the DBMS, histograms have been studied extensively and utilized in the design and implementation of database systems. They are widely used in selectivity estimation for database query optimization, and in approximating query result sizes. A great deal of research work has been done in this area, and we shall not attempt to survey the field here. Various histogram-based algorithms were proposed in [4], [5], [6], [7], and [8]. Also, the optimization of these algorithms was proposed in [9], [7], and [8]. Additionally, the use of sampling in this problem has been addressed in [10] and [11]. New, error-bounded algorithms were proposed in [12], [2], [13], [14], [15], and [1], which form the core of the strategies presented in this paper. While the salient details of these are highlighted presently, a brief survey of the pertinent results will be presented in a later section. A more detailed survey is found in [3] and [1]. The accuracy of the estimates of query result sizes is of fundamental importance in query optimization. Also, it is well known that it has direct influence on choosing optimal QEPs, including the selection of the access paths, the join orders, and the join methods. For example, it has been shown in [16] that errors of the estimates of query result sizes may grow exponentially with the number of joins. In other words, it is (both theoretically, and in real-life systems) one of the most important aspects useful for determining the effectiveness of selecting a hopefully optimal QEP. In this paper, we address the problems of estimating query result sizes in a real-life database system, namely the ORACLE DBMS. As mentioned earlier, Oommen and Thiyagarajah had introduced two new histogram-like techniques, namely the Rectangular Attribute Cardinality Ma