Optimizing large star-schema queries with snowflakes via heuristic-based query rewriting

User queries have been becoming increasingly complex (e.g., involving a large number of joins) as database technology is applied to some application domains such as data warehouses and life sciences. Query optimizers in existing database management systems often suffer from intolerably long optimization time and/or poor optimization results when optimizing large join queries. One possible solution to tackle these problems is to rewrite a user-specified complex query into another form that can better utilize the capability of the underlying query optimizer, based on some heuristic rules, before sending the query to the next query optimization stage. We focus on studying a special type of complex query possessing a star-schema structure with snowflakes, simply called the snow-schema query. The key idea is to split a given snow-schema query into several levels of small query blocks at the query rewriting stage. The query optimizer then optimizes the query blocks and integrates their results into the final query result. A set of heuristic rules on how to divide the query is introduced. A query rewriting framework adopting these heuristics is presented. Experimental results demonstrate that this heuristic-based query rewriting technique is quite promising in optimizing large snow-schema queries.