XML文件树状路径查询之最佳化研究课件.ppt

1、10/13/20221/37DBLAB NTOU大綱n研究動機n系統架構及相關定義n查詢句最佳化處理n實驗結果n結論與未來方向10/13/20222DBLAB NTOU研究動機n結構化合併(Structural Join)的順序nRelational Database,value-based equi-join,two tables and and columnsnXML,structural join,containment relationshipn改善結構化合併的順序n利用最佳化演算法找到不同的結構化合併順序10/13/20223DBLAB NTOU系統架構User I nt er f

2、ace(XQuer y and Resul t)Par si ng XQuer y andBui l di ng XQuer y Tr eeRet r i evi ng Par t i al Dat aRet r i evi ng Fi nal Dat aCombi ni ng Fr agment Pat hBui l di ng Fr agment Pat hXQuer y Tr eeEP-Tr eeEC-Tabl eVal ue I ndexM at ched EC Tupl esResul tBui l di ng Fr agment Pat hTr eeFPTI nput XQuer

3、yOpt i mi zat i on Pr ocess前置前置處理處理最佳化查詢處理最佳化查詢處理將XQuery轉換成XQuery Tree分割成Suffix Path並從相關資料結構取得Partial Data將XQuery Tree轉換成片段路徑樹利用最佳化演算法找出六種走訪順序黏合符合片段路徑的答案將符合片段路徑的答案組成最後的結果自XML文件中取出資料10/13/20224DBLAB NTOUParsing XQuery and Building XQuery TreeFor$p in document(“http:/www.db.cs.ntou.edu.tw/catalog.xml”

4、)/catalogs/catalog/itemWhere$p/author/name/first_name=Germain and$p/publisher/name_of_city=CozumelReturn$p/author/date_of_birth,$p/publisher/name_of_state cat al ogs0cat al og1i t em2aut hor3publ i sher7nam e4dat e_of_bi rt h6nam e_of_st at e9fi rst _nam e5 =Cozumel=Germainnam e_of_ci t y8RootD NG N

5、G NG NCNLNLNLNLN10/13/20225DBLAB NTOURetrieving Partial Datacat al ogs0cat al og1i t em2aut hor3publ i sher7name4dat e_of _bi r t h6name_of _st at e9f i r st _name5 =Cozumel=Germainname_of _ci t y8RootDNGNGNGNCNLNLNLNLN/catalogs/catalog/item/author/name/first_name=Germain/date_of_birth/publisher/nam

6、e_of_city=Cozumel/name_of_staten根據GN、DN、LN來切割出Suffix Path10/13/20226DBLAB NTOURetrieving Partial Data(cont.)2、267、12、31、44、4810、13、328、9、14、342025、27、50、51、59、6317、18、3433、35、36、37、38cat al ogs0cat al og1i t em2aut hor3publ i sher7name4dat e_of _bi r t h6name_of _st at e9f i r st _name5name_of _ci t

7、 y8RootDNGNGNGNCNLNLNLNLN/catalogs/catalog/item/author/name/first_name=Germain/date_of_birth/publisher/name_of_city=Cozumel/name_of_staten利用相關資料結構取得Partial DataPartial Data10/13/20227DBLAB NTOU片段路徑樹(Fragment Path Tree)2、267、12、31、44、4810、13、328、9、14、342025、27、50、51、59、6317、18、3433、35、36、37、38cat al

8、ogs0cat al og1i t em2aut hor3publ i sher7name4dat e_of _bi r t h6name_of _st at e9f i r st _name5name_of _ci t y8RootDNGNGNGNCNLNLNLNLNXQuery Tree10、13、328、9、11、3425、27、50、51、59、6317、18、3433、35、36、37、38aut hor3publ i s her7dat e_of _bi r t h6name_of _s t at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44

9、、48cat al og1i t em2DNGN20f i r s t _name5LN片段路徑樹n透過查詢樹中的GN、DN、LN建構出片段路徑樹n片段路徑樹中的節點代表一Suffix Path10/13/20228DBLAB NTOU片段路徑樹(cont.)n片段路徑n片段路徑的第一個節點為葉節點或分支節點，最後一個節點為根節點或分支節點3、10、134、9、11、3425、27、50、51、59、6317、18、2233、35、36、37、38aut hor3publ i sher7dat e_of _bi r t h6name_of _st at e9name_of _ci t y8GN

10、GNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r st _name5LNfirst_name-authorpublisher-item10/13/20229DBLAB NTOU片段路徑樹(cont.)n片段路徑序列n給予一個片段路徑樹 FPT(FN,FE)，若F1FN為其中的片段路徑，且FE中所有的edge正好被表示一次，則(F1FN)為一組片段路徑序列。3、10、134、9、11、3425、27、50、51、59、6317、18、2233、35、36、37、38aut hor3publ i sher7dat e_of _bi r t

11、h6name_of _st at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r st _name5LNi t em-cat al ogaut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t emfi rst _nam e-aut hor片段路徑序列10/13/202210DBLAB NTOU問題定義n最佳化查詢處理n給予一個片段路徑樹

12、 FPT(FN,FE)，且每一節點NiFN都已取得符合其對應Suffix Path的資料，我們的最佳化查詢處理，會根據經驗法則提出六種適當的結構化合併的順序，使其在建立片段路徑及組合成最後答案時，能有較好的效率。10、13、328、9、11、3425、27、50、51、59、6317、18、3433、35、36、37、38aut hor3publ i sher7dat e_of_bi rt h6nam e_of_st at e9nam e_of_ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20fi rst _nam e5LN片段

13、路徑樹10/13/202211DBLAB NTOU查詢句最佳化處理n最佳化處理模組n根據經驗法則，找出六種結構化合併順序n建立片段路徑模組n將片段路徑中的答案黏合成符合片段路徑的答案n組合片段路徑模組n透過GFP_Table內的答案組出最後的結果n擷取結果模組n自XML文件中取出資料n產生所有可能的路徑n實際產生所有可能的結構化合併順序10/13/202212DBLAB NTOU最佳化處理模組n走訪片段路徑樹n起點：根節點或葉節點n中間點：依partial data數量大小n表示法：(X,Y)nXn根節點：Rn葉節點：S or BnYn中間點：S or Bn六種結構化合併順序nSS,SB,BS

14、,BB,RS,RB3、10、134、9、11、3425、27、50、51、59、6317、18、2233、35、36、37、38aut hor3publ i sher7dat e_of _bi r t h6name_of _st at e9name_of _ci t y8GNGNLNLNLN2、267、12、31、44、48cat al og1i t em2DNGN20f i r st _name5LN10/13/202213DBLAB NTOU最佳化處理模組(cont.)n最佳化處理模組在片段路徑樹上走訪的過程(RB)10、13、328、9、14、3425、27、50、51、59、6317、

15、18、3433、35、36、37、38aut hor3publ i sher7dat e_of_bi rt h6nam e_of_st at e9nam e_of_ci t y8G NG NLNLNLN2、267、12、31、44、48cat al og1i t em2D NG N20fi rst _nam e5LN*catalogitemitem-catalog*item,publisher*author-itemitemauthorauthordate_of_birth*date_of_birth-authorheadpublisheritem*publisherpublisher-ite

16、mname_of_state*name_of_state-publisherauthor-first_nameheadheadpublisher-name_of_cityauthor-first_namepublishername_of_city*name_of_city-publisherfirst_name-authorauthorfirst_nameheadUnVistedListFPListFPSequence*10/13/202214DBLAB NTOU建立片段路徑模組n針對片段路徑序列分別作處理n對片段序列中的每一片段路徑上的節點，其上所帶有的Partial Data資料進黏合，以

17、建立符合片段路徑結構的資料 n利用節點的起始編碼(Start)、結尾編碼(End)、深度編碼(Level)，判斷兩個Suffix Path是否具有適當的結構關係 GFP_Table82010/13/202215DBLAB NTOU建立片段路徑模組(cont.)n經過建立片段路徑模組處理完的片段路經樹及GFP_Table3、10、134、9、11、3425、27、50、51、59、6317、18、2233、35、36、37、38author3publisher7date_of_birth6nam e_of_state9nam e_of_city8G NG NLNLNLN2、267、12、31、4

18、4、48catalog1item2D NG N20first_nam e5LNitemauthorpublisherfirst_nam edate_of_birthnam e_of_citynam e_of_state catalogitem27212263126442648itemauthor787912143134authordate_of_birth82582795095114593463itempublisher71012133132publishernam e_of_state10331335133632373238publiserh nam e_of_city10171318aut

19、horfirst_nam e820G NG NG NLNLNLNLN10/13/202216DBLAB NTOU組合片段路徑模組n依GFP_Table大小，由小至大組合n調整片段路徑序列結構上的關係DoneFPSequenceStructureListUnStructureListfirst_name-authorfirst_nameauthori t em-cat al ogaut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t e

20、mfi rst _nam e-aut hor1234567name_of_city-publisherpublisher-itemauthor-itemitempublisher-itempublishername_of_city-publishername_of_cityitem-catalogname_of_state-publishercatalogname_of_statedate_of_birth-authordate_of_birthi t em-cat al ogaut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ

21、 i shernam e_of_ci t y-publ i sherpubl i sher-i t emfi rst _nam e-aut hor1234567調整好結構關係的片段路徑序列10/13/202217DBLAB NTOU組合片段路徑模組(cont.)i t emaut horpubl i sherf i r st _namedat e_of _bi r t hname_of _ci t yname_of _st at e cat al ogi t em27212263126442648i t emaut hor787912143134aut hordat e_of _bi r t

22、h82582795095114593463i t empubl i sher71012133132publ i shername_of _st at e10331335133632373238publ i ser hname_of _ci t y10171318aut horf i r st _name820GNGNGNLNLNLNLNi t em-cat al ogaut hor-i t emdat e_of_bi rt h-aut hornam e_of_st at e-publ i shernam e_of_ci t y-publ i sherpubl i sher-i t emfi r

23、st _nam e-aut hor1234567NULLResul t Tabl e33252710/13/202218DBLAB NTOU產生所有可能的結構化合併順序n狀態樹(StateTree)n狀態樹節點中放的是片段路徑樹n每個子節點代表片段路徑樹結構化合併的過程ABCD片段路徑樹ABCD狀態路徑樹節點10/13/202219DBLAB NTOU產生所有可能的結構化合併順序(cont.)ABCDABCD10/13/202220DBLAB NTOU實驗n實驗環境nCPU：Pentium 4 2.40GHzn記憶體：512MB n作業系統：Windows 2000 Advanced Serv

24、er n實作工具：Microsoft Visual C+6.010/13/202221DBLAB NTOU實驗相關介紹nData SetsData SetSize#of elementMax depthMax widthXBench-dictionary16MB281387815XBench-customer30MB489601316XBench-catalog100MB2245941710DBLP127MB3332130710TPC-lineitem30MB102297631610/13/202222DBLAB NTOU實驗相關介紹(cont.)n片段路徑樹類型n實驗圖表之表示方式nData

25、Set.Pattern(XBench-catalog.a)nS,B,R,(a)(b)(c)(d)10/13/202223DBLAB NTOU組合順序的分析n分析組合GFP_Table內符合片段路徑答案由小至大的效率是最佳的413240444319269916RB466614684259271315RS471540094057271831BB403140114215270315BS545340324110268716SB617247034031267231SSRandom3Random2Random1PreOrderIncreaseTime(ms)不同組合順序的比較(in XBench-cata

26、log)1110233024022075395RB26798388852119401RS909217720152109387BB2375277411492115399BS1245233920152078406SB812110928592125391SSRandom3Random2Random1PreOrderIncreaseTime(ms)不同組合順序的比較(in lineitem)10/13/202224DBLAB NTOU組合順序的分析(cont.)n組合片段路徑花費的總次數0100002000030000400005000060000700008000090000100000I ncr

27、easePr eO r derRandom 1Random 2Random 3起始點GFP_Table的資料筆數020000040000060000080000010000001200000I ncr easePr eO r derRandom 1Random 2Random 3執行組合次數(in XBench-catalog)(in TPC-lineitem)10/13/202225DBLAB NTOU建立片段路徑模組分析n針對不同的data sets及查詢句類型來進行分析n觀察建立片段路徑處理時間與處理總資料筆數97809800982098409860988099009920SSSBBSR

28、SBBRB建立片段路徑時間(ms)360000360500361000361500362000362500363000363500364000SSSBBSRSBBRB建立片段路徑處理總資料數(in XBench-catalog.a)10/13/202226DBLAB NTOU建立片段路徑模組分析(cont.)269027002710272027302740275027602770SSSBRSBSBBRB建立片段路徑時間(ms)105000105200105400105600105800106000106200106400106600106800SSSBRSBSBBRB建立片段路徑處理總資料數(

29、in XBench-catalog.b)10/13/202227DBLAB NTOU建立片段路徑模組分析(cont.)(in XBench-catalog.c)5824582658285830583258345836583858405842SSSBRSBSBBRB建立片段路徑時間(ms)150740150760150780150800150820150840150860150880150900150920150940SSSBRSBSBBRB建立片段路徑處理總資料數10/13/202228DBLAB NTOU建立片段路徑模組分析(cont.)123501240012450125001255012

30、6001265012700SSSBBSRSBBRB建立片段路徑時間(ms)490000491000492000493000494000495000496000SSSBBSRSBBRB建立片段路徑處理資料筆數(in XBench-catalog.d)10/13/202229DBLAB NTOU建立片段路徑模組分析(cont.)2150217522002225225022752300SSSBBSBBRSRB建立片段路徑時間(ms)835008360083700838008390084000SSSBBSBBRSRB建立片段路徑處理筆數(in TPC-lineitem.b)10/13/202230DB

31、LAB NTOU建立片段路徑模組分析(cont.)40004020404040604080410041204140416041804200SSSBBBRSBSRB建立片段路徑時間(ms)169500169525169550169575169600169625169650169675169700SSSBBBRSBSRB建立片段路徑處理資料筆數(in DBLP.b)10/13/202231DBLAB NTOU建立片段路徑模組分析(cont.)148001485014900149501500015050SSSBBSBBRSRB建立片段路徑時間(ms)5555005560005565005570005

32、57500558000558500559000559500560000560500SSSBBSBBRSRB建立片段路徑處理資料筆數(in DBLP.b)10/13/202232DBLAB NTOU最佳化查詢系統比較n最佳演算法的六種走訪順序nSS,SB,BS,BB,RS,RBn論文李03系統nPren產生所有可能走訪順序系統nBest,Worstn組合時採用由小至大的方式10/13/202233DBLAB NTOU最佳化查詢系統比較(cont.)時間(ms)BestSSSBBSBBRSRBWorstPreXQuery011405214061(2)14060(1)14101(3)14130(5)

33、14105(4)14130(5)1413516653(6)XQuery0243564360(1)4360(1)4395(3)4401(4)4375(2)4404(5)44065095(6)XQuery0394679470(1)9472(2)9476(4)9480(5)9475(3)9480(5)948310467(6)XQuery041911719156(1)19156(1)19219(3)19326(5)19222(4)19327(6)1933719938(7)XQuery0585338536(1)8536(1)8543(4)8553(5)8540(3)8557(6)85609775(7)X

34、Query0618591859(1)1859(1)1885(4)1869(2)1870(3)1885(5)18862276(6)XQuery07220220(1)220(1)223(2)225(3)223(2)223(3)225226(4)10/13/202234DBLAB NTOU最佳化查詢系統比較(cont.)時間(ms)BestSSSBBSBBRSRBWorstPreXQuery08217217(1)217(1)229(2)250(3)229(2)250(3)250256(4)XQuery09785787(1)787(1)792(4)790(3)789(2)792(4)795806(5)

35、XQuery101442014420(1)14420(1)14438(3)14440(4)14422(2)14441(5)1444316110(6)XQuery1157245724(1)5724(1)5724(1)5724(1)5727(2)5727(2)57296170(3)XQuery1299689968(1)9968(1)9968(1)9968(1)9968(1)9968(1)996811191(2)XQuery132787927890(1)27890(1)27922(2)27929(3)27960(4)28023(5)2804529627(6)10/13/202235DBLAB NTOU結論與未來方向n最佳化查詢演算法nSS,SB BS,RS BB,RBn根據經驗法則提出六種適當的結構化合併順序，且接近最佳的查詢處理效率n未來研究方向n根據cost model找出更精確的結構化合併順序10/13/202236DBLAB NTOUEnd謝謝大家10/13/202237DBLAB NTOU