On-line methods for database optimization
Lipyeow Lim, Jeffrey Scott Vitter · 2004
Databases and information retrieval systems storing data from the World Wide Web require new optimization strategies to deal with the different types of data (textual, semi-structured and relational), the massiveness of the data, and the dynamic nature of the data. This dissertation investigates on-line methods for the optimization of databases storing web data. On-line methods avoid access to the underlying data, avoid the rebuilding of data structures from scratch, and adapt to changes in the data and query workload characteristics. On-line techniques are therefore especially suited to web data. In this dissertation, we present on-line techniques for two general problems: how to update inverted indexes and how to estimate the selectivity or result size of queries in database systems. For the index update problem, we present the landmark-diff method for updating the inverted index in response to changes in previously indexed documents. The landmark-diff method allows indexes to be updated incrementally without a complete rebuild. For selectivity estimation, we propose three on-line techniques that address the selectivity estimation problem in three different context. In the context of relational databases, we present SASH, a Self-Adapting Set of Histograms, that uses probabilistic graphical models to address the following issues in an on-line manner: which sets of attributes to build histograms on, how to build these histograms without looking at data, and how much memory should be allocated to these histograms. For XML native databases, we present XPathLearner, an on-line workload-aware method for estimating the result size of given XPath queries. XPathLearner learns the path statistics from query feedback (past query answers) in an on-line manner, and adapts itself to changes in the data and the query workload characteristics. In a more general context, we present CXHist, an on-line classification based histogram for estimating the selectivity of a broad class of queries. CXHist models queries instead of data and stores the mapping between queries and their selectivity using a naive Bayesian classifier. We show that CXHist is very accurate in estimating the selectivity of exact match and substring predicates on leaf values reachable by a given XPath in XML databases.