Query result estimation in databases.

摘要

Query size estimation plays an important role in the query optimizer of a database management system. For example, depending on the size of the intermediate results, a particular query execution plan may be favored over another. Query estimates can also be used by the database system to give user feedback on the possible result sizes and the running time needed before the queries are executed. In this thesis, we discuss a variety of estimation techniques that can be applied in various database applications. We will cover estimation techniques developed for special purpose database systems (e.g., time-series database and data cubes) and estimation techniques for queries in conventional relation database systems. In particular, we first discuss estimation techniques for similarity search in time-series databases using the Discrete Fourier Transform (DFT) and the Discrete Wavelet Transform (DWT). Second, we demonstrate our technique which applies the DWT for progressive and approximate aggregate range query processing in data cubes. Third, we present a sampling technique based on the golden rule of sampling, introduced by von Neumann in 1947, for estimating range queries in relational databases. We also extend this sampling techniques to spatial and multidimensional datasets. Finally, we propose novel extensions that can adapt user query patterns for more accurate estimate of the size of selection or range queries in relational databases.