多條件分頁(yè)查詢(xún)優(yōu)化的設(shè)計(jì)方法

1、多條件分頁(yè)查詢(xún)優(yōu)化的設(shè)計(jì)方法第36卷Vo1.36第2期No.2計(jì)算機(jī)工程ComputerEngineering2010年1月January2010?軟件技術(shù)與數(shù)據(jù)庫(kù)?文章編號(hào)t1000-3428(2010)02-0051-02文獻(xiàn)標(biāo)識(shí)碼tA中田分類(lèi)號(hào).TP311多條件分頁(yè)查詢(xún)優(yōu)化的設(shè)計(jì)方法李輝,王墻波(北京化工大學(xué)信息科學(xué)與技術(shù)學(xué)院,北京100029)摘要:隨著數(shù)據(jù)量的不斷增加,數(shù)據(jù)庫(kù)的分頁(yè)查詢(xún)效率成為提高數(shù)據(jù)庫(kù)訪問(wèn)性能的重要問(wèn)題.從分析影響分頁(yè)查詢(xún)速度的關(guān)鍵因素入手,結(jié)合優(yōu)化器中SQL語(yǔ)句的優(yōu)化原理和分頁(yè)算法,通過(guò)理論推導(dǎo)和實(shí)驗(yàn)結(jié)果的分析,提出分頁(yè)查詢(xún)優(yōu)化的設(shè)計(jì)方法.將該方法應(yīng)用于實(shí)際系統(tǒng)的

2、分頁(yè)框架中,取得了較好的效果.關(guān)健詞:優(yōu)化器;查詢(xún)優(yōu)化;分頁(yè)框架DesignMethodsofMulti?conditionPagingQueryOptimizationLIHui.WANGRui-bo(CollegeofInformationScienceandTechnology,BeijingUniversityofChemicalTechnology,Beijing100029)AbstractWiththeincreasingamountofdata,pagingqueryefficiencyofdatabasebecomesanimportantissuetoimprovethea

3、ccessperformanceofdatabase.Thispaperbeginswiththeanalysisofkeyfactorswhichimpactthespeedofpagingquery,combiningwiththeoptimizationtheoryofSQLstatementintheoptimizeddeviceandpagingalgorithms,andthroughtheanalysisoftheoreticalinfersandexperimentalresults,topointoutdesignmethodsofpagingqueryoptimizatio

4、n.Itachievesgoodresultstoimplythemethodsintopagingframeworkofactualsystems.Keywordsoptimizer;queryoptimization;pagingframework數(shù)據(jù)庫(kù)查詢(xún)是數(shù)據(jù)庫(kù)的核心操作.在查詢(xún)中,查詢(xún)優(yōu)化是利用查詢(xún)優(yōu)化器對(duì)SQL語(yǔ)句進(jìn)行優(yōu)化,并使SQL執(zhí)行代價(jià)最小.文獻(xiàn)【2】從SQL角度,闡述SQL查詢(xún)語(yǔ)句高效執(zhí)行方法.文獻(xiàn)【3】介紹查詢(xún)表達(dá)式優(yōu)化的一般過(guò)程,在查詢(xún)重寫(xiě)階段提出一種面向?qū)ο蟮目蚣?設(shè)計(jì)并實(shí)現(xiàn)了"多字段間關(guān)系自動(dòng)推理"等若干種優(yōu)化方法.上述方法在優(yōu)化查詢(xún)語(yǔ)句上起很大

5、作用.隨著關(guān)系數(shù)據(jù)庫(kù)在B/S體系結(jié)構(gòu)上的廣泛應(yīng)用,龐大的數(shù)據(jù)很難在一頁(yè)顯示,為了進(jìn)一步提高數(shù)據(jù)量達(dá)到千萬(wàn)條以上的分頁(yè)查詢(xún)速度,尋找高效率分頁(yè)方法是十分必要的.1分頁(yè)查詢(xún)優(yōu)化方法數(shù)據(jù)庫(kù)分頁(yè)查詢(xún)處理的開(kāi)銷(xiāo)通常取決于2個(gè)方面:一是磁盤(pán)讀寫(xiě)的I/O次數(shù);二是CPU的處理時(shí)間.1.1減少蠢盤(pán)讀寫(xiě)的I/O次數(shù)的方法數(shù)據(jù)的查詢(xún)處理的代價(jià)通常取決于對(duì)磁盤(pán)的訪問(wèn),因?yàn)榇疟P(pán)比內(nèi)存的訪問(wèn)速度慢.因此,應(yīng)該盡量減少對(duì)I/O設(shè)備的訪問(wèn)或者提高I/O設(shè)備訪問(wèn)的并發(fā)率.提高數(shù)據(jù)庫(kù)系統(tǒng)效率的有效方法是建立聚焦索引.聚焦索引的建立,使得關(guān)系中數(shù)據(jù)的邏輯順序和在磁盤(pán)上的物理存儲(chǔ)順序數(shù)據(jù)相鄰排列,使得SQL語(yǔ)句在檢索時(shí),只檢索索引

6、項(xiàng)有效范圍內(nèi)的數(shù)據(jù),而對(duì)于超出索引項(xiàng)值的數(shù)據(jù)SQL語(yǔ)句將不再訪問(wèn),這樣就減少了數(shù)據(jù)的訪問(wèn)量及訪問(wèn)次數(shù),提高了查詢(xún)效率O對(duì)于執(zhí)行一個(gè)形式為(r)的選擇操作,如果在關(guān)系attr上無(wú)索引,除了掃描整個(gè)關(guān)系r之外可能沒(méi)有其他的選擇,假定關(guān)系r占據(jù)的磁盤(pán)頁(yè)數(shù)為F,那么這個(gè)過(guò)程需要F次傳輸.然而,如果在attr上建立聚焦索引,那么可以通過(guò)二分搜索找到關(guān)系r中滿(mǎn)足attr=value的第1個(gè)元組所在的頁(yè);然后向著恰當(dāng)?shù)姆较驋呙杓纯色@得滿(mǎn)足attropvalue的元組,這樣一次二分搜索的開(kāi)銷(xiāo)約為lbF.如果關(guān)系r占據(jù)500頁(yè),則搜索開(kāi)銷(xiāo)為1b500,也就是9次傳輸,而無(wú)索引的情況則需要500次,大大減小了I/

7、O次數(shù).1.2堿少CPU的處理時(shí)間的方法減少計(jì)算機(jī)系統(tǒng)需要計(jì)算的數(shù)據(jù),使CPU的代價(jià)降到最低,對(duì)于查詢(xún)分頁(yè)效率來(lái)講,主要表現(xiàn)在2個(gè)方面:一是減少SQL的執(zhí)行代價(jià),因?yàn)镾QL語(yǔ)句的一個(gè)特點(diǎn)是同一個(gè)查詢(xún)對(duì)象,不同SQL語(yǔ)言在實(shí)現(xiàn)方式之間的執(zhí)行效率上的差異,需要分析優(yōu)化器的工作原理,選取最有效的SQL語(yǔ)句J.二是尋找查詢(xún)效率最高的分頁(yè)方法.1.2.1多條件組合查詢(xún)的SQL優(yōu)化算法在所開(kāi)發(fā)的項(xiàng)目中常常需要對(duì)輸入條件進(jìn)行動(dòng)態(tài)組合查詢(xún),如果輸入A1,A22個(gè)查詢(xún)條件,其中有A1,A2,A1A2和無(wú)條件輸入共4種組合(2個(gè)).假設(shè)輸入條件為個(gè),每一個(gè)條件取2個(gè)值,對(duì)輸入數(shù)據(jù)的查詢(xún)按"1"

8、處理,不輸入數(shù)據(jù)的查詢(xún)條件按"0"處理,按照乘法原理其組合結(jié)果為2,若程序中對(duì)每一個(gè)結(jié)果判斷一次,當(dāng)輸入10個(gè)查詢(xún)條件時(shí),判斷語(yǔ)句達(dá)到2個(gè),程序的代碼量非常龐大且效率很低.改進(jìn)的優(yōu)化算法具體實(shí)施如下:(1)初始化一個(gè)變量(result),用來(lái)保存組合條件結(jié)果.(2)對(duì)首個(gè)查詢(xún)進(jìn)行判斷,如果該查詢(xún)條件不為空,則result等于where與查詢(xún)條件的組合.(3)依次對(duì)后續(xù)查詢(xún)條件進(jìn)行判斷,如果查詢(xún)條件為空,基金項(xiàng)目:國(guó)家"十一五"科技支撐計(jì)劃基金資助項(xiàng)目(2006BAK31B04)作者倚介:李輝(1975一),男,副教授,博士,主研方向:信息安全,數(shù)據(jù)庫(kù)理論

9、及應(yīng)用;王瑞波,碩士收稿日期:20090720E-mall: 一5l一則result等于where與查詢(xún)條件的組合,否則為result與新查詢(xún)條件的組合.(4)得到所有組合條件的累加值result,將累加值加入到SQL查詢(xún)語(yǔ)句中,即為所有組合查詢(xún)條件的最終查詢(xún)語(yǔ)句.在該算法中,對(duì)每一個(gè)查詢(xún)都進(jìn)行歸一化處理.先對(duì)每個(gè)組合進(jìn)行條件判斷,為空和不為空,都只有一個(gè)輸出條件,該輸出條件將累加到下一個(gè)輸入條件中.通過(guò)簡(jiǎn)化后,輸入的個(gè)查詢(xún)條件,其查詢(xún)語(yǔ)句的結(jié)果為,且算法中跟邏輯關(guān)系的處理無(wú)關(guān),可以是"and","or","&a

10、mp;gt;=","like","<>","<="等中的一種或幾種,共邏輯關(guān)系的取舍根據(jù)查詢(xún)需求來(lái)決定.具體流程如圖1所示.圈1多條件組合查詢(xún)漉程1.2.2窗口型分頁(yè)模型方法分頁(yè)是每個(gè)Web應(yīng)用程序都要面對(duì)的一個(gè)問(wèn)題.對(duì)于小型的應(yīng)用,可以采取傳統(tǒng)的分頁(yè)方法,比如對(duì)于每次請(qǐng)求都從數(shù)據(jù)源直接提取數(shù)據(jù),這樣做簡(jiǎn)單易行,不失為一個(gè)較好的解決方案;對(duì)于規(guī)模較大的應(yīng)用程序,每一個(gè)頁(yè)面都牽扯到大量的數(shù)據(jù)庫(kù)訪問(wèn),需要如何定制好的分頁(yè)策略緩存頁(yè)面是值得研究的問(wèn)題.窗口型分頁(yè)模型是應(yīng)用最為廣泛的一種分頁(yè)

11、模型,其基本模式是根據(jù)當(dāng)前頁(yè)碼把附近的幾頁(yè)(一般是lO頁(yè)左右)都作為鏈接放在頁(yè)面上.該算法的直觀思路是通過(guò)反復(fù)模擬每一個(gè)人點(diǎn)擊頁(yè)面的隨機(jī)行為得到一個(gè)統(tǒng)計(jì)意義上的頁(yè)面訪問(wèn)率,根據(jù)訪問(wèn)率的大小來(lái)控制緩沖區(qū)間的大小,和傳統(tǒng)的僅提高頁(yè)面緩沖數(shù)量做法相比,有較小的應(yīng)用程序的內(nèi)存開(kāi)銷(xiāo),提高了速度.假設(shè)一共有個(gè)頁(yè)面,頁(yè)面窗口的大小為w,當(dāng)前頁(yè)為,頁(yè)面被訪問(wèn)的概率以為中心服從正態(tài)分布,如式(1)所示,當(dāng)窗13超過(guò)邊界時(shí),適當(dāng)?shù)仄揭拼翱?概率計(jì)算公式保持不變.:川.1只=ex.xM,M一+¨l-,/2rtO"2252可以通過(guò)計(jì)算機(jī)模擬的方法求得圖2,模擬程序?qū)υL問(wèn)概率進(jìn)行規(guī)一化處理.禱鞋0.

12、40.302OlO00M頁(yè)圖2宙口分頁(yè)模型楱|奠圈等于3,等于30,窗口大小為1O,每個(gè)虛擬用戶(hù)從第1頁(yè)出發(fā)翻頁(yè)10次.結(jié)合平時(shí)的使用經(jīng)驗(yàn),這個(gè)概率密度圖跟實(shí)際的情況比較接近.對(duì)于窗13型分頁(yè)模型,概率密度比較均勻,所以緩沖區(qū)間取得對(duì)稱(chēng)即可,當(dāng)前頁(yè)碼M比較小的時(shí)候可以把緩沖區(qū)間開(kāi)得大一些,當(dāng)M比較大的時(shí)候(比如M>10),相應(yīng)地減小緩沖區(qū)間.這種方法有2個(gè)優(yōu)點(diǎn):(1)能合理地控制內(nèi)存的占用量;(2)有效合理地控制了緩沖作用范圍.對(duì)于被經(jīng)常訪問(wèn)的頁(yè)碼,盡可能多地緩沖,對(duì)于很少被訪問(wèn)的頁(yè)碼,緩沖甚至不緩沖,同時(shí)也極大地限制了數(shù)據(jù)不一致等情況.通過(guò)訪問(wèn)概率分析,可以設(shè)計(jì)出具有不同策略的

13、頁(yè)面緩沖器,滿(mǎn)足不同應(yīng)用的需求,比盲目地提高緩沖數(shù)量效果要好得多.2性能測(cè)試驗(yàn)證為對(duì)優(yōu)化后的算法性能提升情況進(jìn)行驗(yàn)證,新建User表,對(duì)于selectfromUserwherename=Aandage=Bandsex=C查詢(xún)語(yǔ)句,模擬用戶(hù)點(diǎn)擊窗口分頁(yè)模型上的連接,并記錄系統(tǒng)反應(yīng)的時(shí)間.測(cè)試環(huán)境:Web服務(wù)器和測(cè)試運(yùn)行在PC機(jī)上(2.53GHz/768MB),數(shù)據(jù)庫(kù)使用SQLServer2000,數(shù)據(jù)庫(kù)服務(wù)器是Tomcat5.5.23,記錄行數(shù)1萬(wàn)行.分別以3,10,100,1000,2000,5000,10000,20000,30000,40000,50000頁(yè)數(shù)為例,和傳統(tǒng)方法對(duì)比進(jìn)行速度測(cè)

14、試,如表1所示.表1試結(jié)果比較頁(yè)數(shù)傳統(tǒng)方法測(cè)試時(shí)問(wèn)/ms改進(jìn)方法測(cè)試時(shí)問(wèn)/ms從表1中可以看出,傳統(tǒng)方法在分頁(yè)較少的情況下查詢(xún)速度可以接受.但大于1000頁(yè)時(shí)改進(jìn)方法的查詢(xún)分頁(yè)速度明顯要比傳統(tǒng)方法快很多.在實(shí)際當(dāng)中,尤其在大數(shù)據(jù)量的情況之下,傳統(tǒng)方法會(huì)導(dǎo)致超時(shí),使數(shù)據(jù)無(wú)法顯示出來(lái).3結(jié)束語(yǔ)通過(guò)上述分析可知,要提高分頁(yè)查詢(xún)效率,減少查詢(xún)時(shí)間,就是要在SQL結(jié)果正確的前提下,用優(yōu)化器可以識(shí)別的語(yǔ)句,充分利用索引,減少表的掃描的UO次數(shù),盡可能避免表搜索的發(fā)生,減少數(shù)據(jù)傳輸數(shù)量.同時(shí)還要尋求高效的分頁(yè)算法,并且能夠使麗者有機(jī)地結(jié)合起來(lái),最終達(dá)到用戶(hù)對(duì)分頁(yè)速度的需求.(下轉(zhuǎn)第55頁(yè))對(duì)于以上horn短

15、句集,有下式:D()÷一C()vB(x)罩曰()uC()D(x)(3)設(shè)D),C(),),尺,),)為原子謂詞公式,有:C(y)÷-R(x,),)D(x)E(C(),)÷-n(x,y)D(x)借助上面VR.C的結(jié)論得到:C()n(x,),)D()iDVR.C(4)借助上面妒jR.C的結(jié)論得到:D()÷-R(x,),)C(y)§3R.CD(5)基于以上的映射規(guī)則,對(duì)于用UML建模的規(guī)則采用AL-languages中的ALUE作為形式化的描述手段.(1)屬于某個(gè)類(lèi)構(gòu)造型variable的變量名泛指任意滿(mǎn)足該規(guī)則的對(duì)象,用原子概念形式化描述.(2)關(guān)

16、聯(lián)表達(dá)的屬性,用原子關(guān)系形式化描述.(3)如果出現(xiàn)在關(guān)聯(lián)當(dāng)中的變量沒(méi)有定義其所在類(lèi),在基于DL的形式化描述中,論域要對(duì)這個(gè)變量所屬的概念進(jìn)行說(shuō)明.(4)某些規(guī)則會(huì)用到具體的對(duì)象或常量,在DL公理的基礎(chǔ)上引入ABox對(duì)其形式化.ABox的解釋,的論域必須包含UML圖中出現(xiàn)的所有對(duì)象,解釋函數(shù)將DL的對(duì)象名映射到相應(yīng)的UML對(duì)象.倒1fmen(y)'一haschild(,y)Amotherwithson(x)lmother(x)卜motherwithson()mother(x)(menCy)÷_haschild,),)÷_motherwithson)根據(jù)式(2),式(4

17、)及形式化描述規(guī)則,以上規(guī)則集可轉(zhuǎn)化為:motherwithsonmotherAVhasChildanenmen=yly是UML定義的類(lèi)men的對(duì)象mother=xlx是UML定義的類(lèi)mother的對(duì)象=mumother對(duì)例1的形式化描述如圖4所示.'I'''<.<.v.''i.ab.le.>.>I;翌塑I廣1I._J圈爭(zhēng)圉圈4偽1形式化描述例2heart(z)haslocation(x,z)÷一aorticvalve(y)haslocation)(上接第52頁(yè))參考文獻(xiàn)【1】常偉

18、.SQL中查詢(xún)語(yǔ)句的優(yōu)化方法J】.重慶工學(xué)院,2006,2O(5):8588.以上規(guī)則可用描述邏輯形式化地表達(dá)為3haslocation.aorticvalvejhaslocation.heartaorticvalve=yly是類(lèi)aorticvalve的對(duì)象arf=zlz是類(lèi)hean的對(duì)象lA=aorticvalveuhearuxl<,y>滿(mǎn)足haslocation關(guān)聯(lián)yEaorticvalve對(duì)例2的形式化描述如圖5所示.圈5明2形式化描述5結(jié)束語(yǔ)將UML用于本體建模的研究可以圍繞特定的本體描述語(yǔ)言展開(kāi).公理集是基于本體的知識(shí)庫(kù)的重要組成部分.實(shí)現(xiàn)本體公理集的圖形

19、化建模有助于擴(kuò)展本體的應(yīng)用范圍,提高本體的建模效率.本文設(shè)計(jì)了改進(jìn)的SWRL元模型,為規(guī)則設(shè)計(jì)了基于UML的建模方法,解決了文獻(xiàn)【4】中建模方法難以描述規(guī)則前件中OWL類(lèi)實(shí)例的問(wèn)題.對(duì)于部分圖形化建模的規(guī)則,論證了用描述邏輯對(duì)其形式化的可行性.通過(guò)將這部分基于UMLprofile建模的規(guī)則翻譯為描述邏輯,說(shuō)明本文的建模方法有更強(qiáng)的表達(dá)能力.下一步的工作包括如何針對(duì)圖形化建模的規(guī)則進(jìn)行推理,以便利用本體檢測(cè)實(shí)現(xiàn)UML檢驗(yàn),給出了基于描述邏輯對(duì)其形式化的方法,為這項(xiàng)研究工作提供了形式化的邏輯基礎(chǔ).參考文獻(xiàn)【1】鐘凌燕,陳崗.OWLDL的UML建模方法【J.計(jì)算機(jī)工程,2006,32(21):5860.2HorrocksI,BoleyH.SWRL:ASemanticWebRuleLanguageCombiningOWLandRuleM