ETL执行过程的优化研究

计算机科学2007Vol. 34No. 1ETL执行过程的优化研究*)吴远红(浙江海洋学院信息学院舟山 316004)摘要提出了一个ETL(Exrction: Transformation-Loading)优化框架并对ETL过程的逻辑优化进行了研究,把优化问题建模成状态空间搜索问题。每个ETL工作流看作-种状态,通过一系列正确的状态变换来构造状态空间,并且提出算法来获得最小执行时间的ETL工作流。理论分析和实践表明其具有良好效果。关键词ETL,工作流,优化The Research of Optimizing ETL Execution ProcessWU YuanrHong(Information College of Zhejiang Ocean University, Zhoushan 316004)Abstract An optimization framework is provided in the paper ,and the logical optimization of ETL processes is researched. The optimization problem is modeled as a state space search problem. Each ETL workflow is considered as astate and the state space is fabricated through a set of correct state transitions. Moreover，algorithms are provided to-wards the minimization of the execution cost of an ETL workflow . The theory and experiment result prove it to be effi-cient.Keywords ETL, Workflow ,Optimization算法,理论和实践表明这种方法对于海量数据的处理很有效。1前言ETL过程不能单纯地作为一个大的查询交给数据库去数据仓库作为一-种数据 密集型应用，由两部分构成:静态处理.去优化。为此提出如图1所示的ETL执行优化框架,部分和动态部分,静态部分是指数据仓库的体系架构和实例它由ETL过程设计器、优化器、调度抽取.转换、加载等几种数据,动态部分是构建和维护数据仓库的各种进程，负责加类型的活动组成,其中ETL执行优化主要是寻求一个和原载、刷新等,这主要由ETL工具完成。ETL 负责将分布的、ETL过程等价的、最小执行代价的ETL过程。其处理过程异构的数据源数据(如关系数据文本数据.XML.HTML等)如下:由ETL过程设计器设计好ETL过程,提交给优化器，抽取到临时中间层(Data Staging Area), 在中间层进行清洗、通过转换规则进行等价状态变换生成状态空间，再由算法根转换集成,然后加载到数据仓库，成为决策支持(如OLAP,据代价模型进行状态空间搜索获得最小执行代价ETL工作数据挖掘)的基础。ETL 作为一种数据转换和集成的工具，流。是构建数据仓库的基本工具。2问题建模。 用户界面.I EnL执行优化器I ETL过程执行交互等价状态的状态空间生戚.转换规附ETL工作流的优化问题可建模成状态空间搜索问题:每|元数据管理工具一个状态是- -个ETL工作流图,对每个状态采用状态变换产状态空间搜索量小代价状态.手代价模型Emu过程设计舞生所有可能的等价状态，从中找出代价最小的状态即为最优ETL执行过程。转换活动调度悬2.1 EIL 工作流的形式化定义广抽取器活动是一-个四元组A=(ID,I,O,S), ID是活动标识符,元数抛库I是输入模式的集合,0是输出模式的集合,S是-个或多个扩展的关系代数表达式,表示每个输出模式的语义。转换源中间层转换目标每个ETL工作流看作-一个状态也就是- - 个有向无环图(DAG图),图的节点可以是ETL活动和记录集,边代表数据图1 ETL执行优化框架图供给关系。目前对它的研究主要在ETL过程的建模1.43 ,但对ETL假定有活动集A.记录集RS,供给关系集Pr ,ETL工作过程优化的研究却不多,它不同于多查询优化们,因为多查询流可中国煤化Iv,E),V=AURS,E=优化主要着眼于将各个不同的查询语句局部最优化,而在Pr.HCN M H G给每一个活动赋值唯ETL过程中,各个活动相互关联,全局优化是必须考虑的。一的执行优无权作为结 切杯不付。本文提出一种ETL优化执行框架,并给出具体的优化过程和2.2转换规则* )基金项目:浙江省教育厅项目(0050113);浙江海洋学院项目(X05LQ07)。昊远红讲师,硕士,研究方向;数据抽取、数据挖掘。●81●接下来引人状态的一系列逻辑转换。表达式S'= T(S)活动分配到两个并行分支里来提高效率。这两种变换分别记表示从状态s到s'的变换,这些逻辑转换包括:为FAC(as ,a1 ,az)和DIS( ar, a)如图2(b)。FAC与DIS本.1)SWA变换:交换一元活动an ,az在图中的顺序,记为质上是对-元和二元活动进行交换。SWA(al,ar)如图2(a),这样可以把选择频率高的活动推向3)MER与SPL变换:用这两个变换来组合活动和取消工作流的开端,类似于传统的代数优化。组合而不改变它们的语义。这两种变換分别记为MER2)FAC与DIS变换: FAC把汇聚前在汇聚的两个分支(a1+z ,an ,az)和SPL(a1+2 ,a1 ,a2)如图2(C)。这样搜索空间里各做了一次即两次操作,放在汇聚后做一次。DIS把一个可以大大减少。8SWA(a,2) |SWA(2曲)MER(arzhag)↓↑SPL(国z剧雨)FACaa2) |↑ DIS(B,回)| a142 .a>- >(细) SWA .(b) FAC and DIS(C) MER and SPL图2状态的逻辑变换2.3 代价模型s'=SGen(s);,unvisited- -s'给定活动a, C(a)代表a的代价(不仅和代价模型有关而且和活动在工作流中所处的位置有关) ,C(a)代价评估可visited←-S以采用查询优化的各种代价模型。整个状态的代价是它所有5. return SMN活动的代价和。6. End.C(S)= gc(a;)3.2 启发式算法首先对搜索空间的每-一个状态利用元数据库的统计信息为了避免搜索整个状态空间,采用启发式算法进行改进，进行代价评估。最优化ETL工作流问题就是找到一个状态转换前对工作流可以约束的活动进行MER变换;接着HS找SMEN ,C(Smav )最小。到初始状态中所有的同类活动(H)和可分解活动(D) ,然后把2.4 元数据库初始状态S0分组(L);仅在线性路径中应用SWAP变换;对主要保存ETL过程的元数据和临时中间层中数据库概处于两个汇聚流的同类活动应用FAC变换;在转换适用性允貌的统计描述,包括模型信息、表定义、视图、用户自定义类型许的情况下应用DIS变换;仅在前面用FAC变换和DIS变换和函数约束等等。ETL 执行优化器在生成执行计划时将其产生的新状态的线性路径中再次应用SWAP变换;最后返回作为定量分析的参考,通常包括元组的数目,属性的大小,和最小代价状态SMav。对于不同属性的不同值的数目。为了保证基本统计信息的正下面是其实现算法。确性,需要不断地修改元数据库中的相关内容。算法Heuristic Search (HS)3基于算法的状态空间搜索输入:初始状态S,即图G= {V,E)和在预处理中用到的-系列合并3.1 穷举法输出:最小代价状态SMaN在穷举搜索法中,对每个状态采用状态变换产生所有可首先对工作流可以约束的活动进行合并MER变换Unvisited-. s能的状态,并把状态空间抽象成图，节点代表状态,边代表状visited- 0态间的转换。穷举搜索算法设置已访问节点集合保存已经访SMNSO问节点和未访问节点集合保存未访问节点,算法从未访问节D-Find Distributable- Activivities(So);L+ -Find_ Local Groups(So);点集合中取出一个未访问状态,产生它的经过状态变化后的.“ For each gi in L{状态进行进- -步处理。算法产生所有可能的状态,然后从所For each pair(ai,aj)in gi{有已访问状态中找出代价最小的状态,即为问题的解。算法TH(c(Smw)