Ph.D. / Computer Science and Engineering / Join-order optimization plays a central role in the processing of relational database queries. This dissertation presents two new algorithms for join-order optimization: a deterministic, exhaustive-search algorithm, and a stochastic algorithm that is based on the deterministic one. The deterministic algorithm achieves new complexity bounds for exhaustive search in join-order optimization; and in timing tests, both algorithms are shown to run many times faster than their predecessors. In addition, these new, fast algorithms search a larger space of join orders than is customary in join-order optimization. Not only do they consider all the so-called bushy join orders, rather than just the left-deep ones, but-what is more unusual-they also consider all join orders that contain Cartesian products. The novel construction of these algorithms enables them to search a space including Cartesian products without paying the performance penalty that is conventionally associated with such a search.
Identifer | oai:union.ndltd.org:OREGON/oai:content.ohsu.edu:etd/586 |
Date | 01 1900 |
Creators | Vance, Bennet |
Publisher | Oregon Health & Science University |
Source Sets | Oregon Health and Science Univ. Library |
Language | English |
Detected Language | English |
Type | Text |
Format | Needs Adobe Acrobat Reader to view., pdf, 13128.903 KB |
Rights | http://www.ohsu.edu/library/etd_rights.shtml |
Page generated in 0.0012 seconds