分層回溯用于數(shù)據(jù)庫的查詢優(yōu)化.pdf

1、數(shù)據(jù)庫商用的巨大成功部分歸功于成熟的查詢優(yōu)化技術(shù).優(yōu)化技術(shù)意味著決定在數(shù)據(jù)庫執(zhí)行查詢語句時(shí)使用哪些索引或者按照什么順序執(zhí)行查詢中的操作等.然后,優(yōu)化器列舉出多種方案,并使用費(fèi)用模型評(píng)估每種方案的代價(jià),選擇代價(jià)最小的方案.一個(gè)優(yōu)化器的核心組件是它的搜索策略或枚舉算法.優(yōu)化器的枚舉算法決定列舉那個(gè)方案,目前最典型的枚舉算法是基于DP(Dynamic Programing)的,現(xiàn)在應(yīng)用于很多數(shù)據(jù)庫系統(tǒng)的優(yōu)化器中.這種算法可以得到較好的優(yōu)化結(jié)果

2、,但是如果要處理復(fù)雜的查詢,需要集成新的查詢技術(shù)或在某特定的執(zhí)行環(huán)境下,其高度復(fù)雜性是不可行的.總的來說,在優(yōu)化算法的高復(fù)雜性和算法產(chǎn)生方案的質(zhì)量之間有一個(gè)權(quán)衡.因?yàn)閷ふ易顑?yōu)方案的問題是NP不可解問題.該文結(jié)合DP算法和回溯法的基本思想,提出了一類新的查詢優(yōu)化算法,并對(duì)該算法進(jìn)行了描述和性能分析.它是基于分層回溯的一種查詢優(yōu)化算法,其優(yōu)點(diǎn)主要在于對(duì)于一些復(fù)雜的應(yīng)用環(huán)境,它在枚舉算法的高復(fù)雜性和算法產(chǎn)生方案的質(zhì)量之間取一個(gè)權(quán)衡點(diǎn),以產(chǎn)生"