列存储系统面向列的连接顺序优化研究-论文.pdf

《列存储系统面向列的连接顺序优化研究-论文.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机研究与发展ISSN1000—1239／CN11-1777门rPJournalofComputerResearchandDevelopment5O(7)：1473-1483，2O13列存储系统面向列的连接顺序优化研究王梅陆戌辰乐嘉锦(东华大学计算机科学与技术学院上海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)摘要连接操作是影响列存储数据查询效率的重要操作之一．对于列存储系统中的连接操作优化，以往的研究工作大多专注于对数据组织结构的优化以及辅助物理结构的建立上，极少涉及逻辑层特别是早期的连接策略优化．为此，根据列存储数据的特点和分析型查询需求的特征，提出了一种新的列存储连接优化方法．该方法采用提早优化的策略，使用“

6、事实表下推”的优化规则，并在多事实表查询条件下引入浓密树进行连接顺序决策，以较小的时空复杂度获得“最优”的连接执行顺序．使用代价估计模型对提出的连接策略优化方法进行了理论验证．同时，在大规模数据仓库基准数据集SSB上通过实验验证了提早优化机制及下推规则的有效性．关键词数据库；列存储；查询优化；连接策略；规则优化中圈法分类号TP311．1随着信息时代数据量的爆炸式增长，在海量数数据量大、查询密集、更加关注对属性而非实体的处据分析处理的需求驱动下，数据仓库、数据挖掘、决理．列存储技术在物理上以列为单位对数据表进策支持等分析型应用迅速发展．此类应用的特点是行拆分，将相同列的数据连续存储，在查询过

7、程中只收稿日期：2011O6—21；修回日期：2012-10—23基金项目：“核高基”国家科技重大专项基金项目(2010ZX01042—001—003—004)；国家自然科学基金项目(61070031，61070032，6l103046)；上海市自然科学基金项目(11ZR1401200)计算机研究与发展2013，5O(7)(a)中相应的JOIN节点内，记录相关异表条件连接略：将选择性最优的节点交换到单表查询子树最左的集合