Abstract. Query optimizers in object-relational database management
systems require users to provide the execution cost models of user-defined
functions(UDFs). Despite this need, however, there has been little work
done to provide such a model. Furthermore, none of the existing work
is self-tuning and, therefore, cannot adapt to changing UDF execution
patterns. This paper addresses this problem by introducing a self-tuning
cost modeling approach based on the quadtree. The quadtree has the
inherent desirable properties to (1) perform fast retrievals, (2) allow for
fast incremental updates (without storing individual data points), and
(3) store information at different resolutions. We take advantage of these
properties of the quadtree and add the following in order to make the
quadtree useful for UDF cost modeling: the abilities to (1) adapt to
changing UDF execution patterns and (2) use limited memory. To this
end, we have developed a novel technique we call the memory-limited
quadtree(MLQ). In MLQ, each instance of UDF execution is mapped to
a query point in a multi-dimensional space. Then, a prediction is made
at the query point, and the actual value at the point is inserted as a new
data point. The quadtree is then used to store summary information of
the data points at different resolutions based on the distribution of the
data points. This information is used to make predictions, guide the insertion
of new data points, and guide the compression of the quadtree
when the memory limit is reached. We have conducted extensive performance
evaluations comparing MLQ with the existing (static) approach.
