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.0019 seconds