資源描述：
《列存儲(chǔ)系統(tǒng)面向列的連接順序優(yōu)化研究-論文.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫(kù)。
1、計(jì)算機(jī)研究與發(fā)展ISSN1000—1239／CN11-1777門rPJournalofComputerResearchandDevelopment5O(7)：1473-1483，2O13列存儲(chǔ)系統(tǒng)面向列的連接順序優(yōu)化研究王梅陸戌辰樂(lè)嘉錦(東華大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院上海201620)(wangmei@dhu．edu．cn)Column—OrientedJoinOrderOptimizationinColumnStoreSystemsWangMei，LuXuchen。andLeJiajin(CollegeofComputerScienceandTechnology，DonghuaUniver
2、sity，Shanghai201620)AbstractJoinisoneofthemostimportantoperationswhichcanlargelyaffecttheefficiencyofcolumnstorebasedqueries．Mostworkoncolumn—storesisfocusedontheimprovingofstoragestructureandthebuildingofphysicalauxiliarystructures，whilethelogicalplanoptimization，especiallyearlyjoinstrategyoptimi
3、zation，hasseldombeenconsideredOnthebasisofthisproblem，thispaperpresentsanewjoinstrategyoptimizationmethodaccordingtothecharacteristicofcolumn—orientedstoragestructureandanalyticalquery．Weadopttheearlyoptimizationstrategyinourmethodandproposea“facttablepush—down”rule．Inparticular，thebushytreestruct
4、urewillbeconsideredinthemulti—fact—tablecasetoreceivea“best”oinpathwithsmal1timeandspacecomplexity．Thenweprovideacostestimationtoverifythecorrectnessoftheproposedjoinstrategyoptimizationmethod．Finally，experimentalresultsonthelarge—scaledatawarehousebenchmarkdatasetsSSBalsoverifytheeffectivenessoft
5、heearlyoptimizationstrategyandtheproposedpush—downrI】】e．Kevwordsdatabase；columnstore；queryoptimization；joinstrategy；rule—basedoptimization(RBO)摘要連接操作是影響列存儲(chǔ)數(shù)據(jù)查詢效率的重要操作之一．對(duì)于列存儲(chǔ)系統(tǒng)中的連接操作優(yōu)化，以往的研究工作大多專注于對(duì)數(shù)據(jù)組織結(jié)構(gòu)的優(yōu)化以及輔助物理結(jié)構(gòu)的建立上，極少涉及邏輯層特別是早期的連接策略優(yōu)化．為此，根據(jù)列存儲(chǔ)數(shù)據(jù)的特點(diǎn)和分析型查詢需求的特征，提出了一種新的列存儲(chǔ)連接優(yōu)化方法．該方法采用提早優(yōu)化的策略，使用“
6、事實(shí)表下推”的優(yōu)化規(guī)則，并在多事實(shí)表查詢條件下引入濃密樹(shù)進(jìn)行連接順序決策，以較小的時(shí)空復(fù)雜度獲得“最優(yōu)”的連接執(zhí)行順序．使用代價(jià)估計(jì)模型對(duì)提出的連接策略優(yōu)化方法進(jìn)行了理論驗(yàn)證．同時(shí)，在大規(guī)模數(shù)據(jù)倉(cāng)庫(kù)基準(zhǔn)數(shù)據(jù)集SSB上通過(guò)實(shí)驗(yàn)驗(yàn)證了提早優(yōu)化機(jī)制及下推規(guī)則的有效性．關(guān)鍵詞數(shù)據(jù)庫(kù)；列存儲(chǔ)；查詢優(yōu)化；連接策略；規(guī)則優(yōu)化中圈法分類號(hào)TP311．1隨著信息時(shí)代數(shù)據(jù)量的爆炸式增長(zhǎng)，在海量數(shù)數(shù)據(jù)量大、查詢密集、更加關(guān)注對(duì)屬性而非實(shí)體的處據(jù)分析處理的需求驅(qū)動(dòng)下，數(shù)據(jù)倉(cāng)庫(kù)、數(shù)據(jù)挖掘、決理．列存儲(chǔ)技術(shù)在物理上以列為單位對(duì)數(shù)據(jù)表進(jìn)策支持等分析型應(yīng)用迅速發(fā)展．此類應(yīng)用的特點(diǎn)是行拆分，將相同列的數(shù)據(jù)連續(xù)存儲(chǔ)，在查詢過(guò)
7、程中只收稿日期：2011O6—21；修回日期：2012-10—23基金項(xiàng)目：“核高基”國(guó)家科技重大專項(xiàng)基金項(xiàng)目(2010ZX01042—001—003—004)；國(guó)家自然科學(xué)基金項(xiàng)目(61070031，61070032，6l103046)；上海市自然科學(xué)基金項(xiàng)目(11ZR1401200)計(jì)算機(jī)研究與發(fā)展2013，5O(7)(a)中相應(yīng)的JOIN節(jié)點(diǎn)內(nèi)，記錄相關(guān)異表?xiàng)l件連接略：將選擇性最優(yōu)的節(jié)點(diǎn)交換到單表查詢子樹(shù)最左的集合
