数据库查询优化中的智能预取技术

1、数据库查询优化中的智能预取技术 0 引言 对于海量数据的检索往往耗时巨大， 因此有必要设计特定的 查询优化系统。 通常的优化系统采用的策略可以分为两类： 通 用的优化策略。该策略与应用本身无关，适应面广，可以应用在 所有的优化系统中， 但往往优化的效果并不是十分明显， 尤其是 对于海量随机检索， 查询效率很难有所提高。 与应用密切相关 的优化策略。 该策略在设计过程中需要考虑应用的细节， 有可能 对查询效率有所提高， 但如果应用比较复杂， 其设计的难度也很 大，而且由于仅适用于特定应用，其开发成本也很高。人工智能 技术具有自适应的特性， 能够针对不同情况自动调整系统的各项 参数，因此十分适合构

2、造一种既与应用相关， 又可以通过自动调 整以适应不同应用的查询优化策略。 通过构建一个采用预取策略的查询优化系统来对数据检索 进行优化。其中预取哪些数据是查询优化系统能否发挥作用的一 个重要因素。 因此在预取数据的选择上采用了蚁群规则和惯性规 则相结合的方式来实现。 通过使用该算法， 预取数据既可以与应 用紧密相关， 同时又具有自动调整的特性， 能够适应不同的应用 需求。通过实验验证， 该方案不仅在特定应用中能够发挥优化作 用，而且具有较强的通用性。 1 相关工作 Seppi1 提出了一种基于 Bayesian 方法的数据查询优化算 法。该算法试图利用人工智能的方法解决查询的不确定性， 在学

3、习算法和查询处理之间获得较好的平衡。 但是这种方法需要大量 的实例进行训练，从而获得相应的Bayesian 网络。然而即使得 到了该网络， 仍然不能处理其他类型应用所产生的查询， 因此在 应用面上受到了很大的限制。基于Seppi 的工作， Cole 等人 2 提出了一种基于成本的决策模型来生成动态执行计划。与 Seppi 进行预测的优化思想不同， Cole 的工作是基于执行成本进行优 化，而相应的执行成本需要建立在预先数据分析的基础上， 这对 负载较重的数据库系统来说会带来较大的性能问题。 WangDazhi 提出了采用分析查询语句， 并提取出相应模板的做法来实现数据 预取 3 。这种思想与本

4、文所提出的预取思想有类似之处，但是 其应用场合仅限于包含大量相同查询模式的场合。例如通过 Web 页面访问数据库， 在该场合下， 访问数据库的模式往往是预先定 义好的，因此比较适合简单的统计预测。 Zhou Jingren 等人 4 则从内存访问的局部化方面入手， 设计了一种新的预测算法， 可 以通过提高在查询过程中内存访问的局部性来提高 Cache 的命 中率。 随着对数据查询需求的日益提高， 查询优化系统已经从单纯 的性能提高发展为具有体系结构、 可扩展的系统。 针对这种发展 趋势，已有研究机构对于查询优化的可扩展性提出了以下几个显 著特征5:具有严格的数学推导和理论算法；具有一套数据 变

5、换规则；基于统计学或成本的模型；算法的物理属性； 新的状态空间搜索策略；执行计划的质量（如是否需要全局搜 索）。 与此同时， 由于现代数据查询都具有海量的特性， 优化器本 身的查询和匹配效率也是十分重要的指标。 目前国外已经开发出 了一些具有可扩展特性的查询优化系统68，但是这些系统并 没有完全满足完整的查询优化需求。 本文提出的方法满足了特征 。虽然并没有提出严格的数学推导，但由于采用了以统计 学为基础的蚁群假设和以 BP网络为基础的惯性假设，仍然具有 比较坚实的理论基础。 2 预取算法描述 本文讨论的目标数据集合为符合关系数据模型的数据源， 面 向的查询语句为标准的 SQL查询语句。？廿丁

6、 ?1标引属性（LP）。 能够对海量数据查询进行分解处理的前提是该海量数据具有可 分性，即存在某个属性值，通过对该属性值进行分类，可以较为 平均地对数据进行分割。 这个值称为标引属性， 记为 LP （ Labled Property ）。 标引属性对于特定的目标数据集合来说是唯一的。 定义2索引属性（IP ）。可能产生数据查询条件的属性称为 索引属性，记为 IP （Indexed Property ）。 目标数据集合除了包括标引属性LP和索引属性IP夕卜，还可 能包括其他属性值。 定义3历史查询（HQ。用户曾经发出的查询请求。其中条 件字段中必须包括LP,有可能包括IP。 根据LP将目标查询数

7、据分解为固定大小的子区域，在每个 子区域上重新构建用户的查询命令，生成的任务称为子查询任 务。每个子查询任务的结果可以形成一个数据块存放到高速缓冲 区中；当下次执行相同的子查询任务时可以直接从高速缓冲区中 获取结果， 而不需要重新执行数据库查询操作， 这样的数据块称 为缓冲块。 定义4用户（U）。每个发出查询请求的客户被称为一个用 户，用 U（ User ）标记。 预取算法的基本思想就是将根据所收集到的HQ来计算未来 可能产生的查询请求， 并通过在空闲时段预取这些查询请求， 将 得到的结果存放在高速缓存中， 以加速对下次查询请求的响应速 度。 本文所涉及的预取技术是在满足以下两个前提的基础上设

8、 计的。 21 蚁群算法 蚁群规则的算法思想如图1所示。图中横坐标为LP，通过 LP将目标数据空间进行等分； 纵坐标为SPs,表示查询语句所返 回的数据属性项， 每种属性项占一格。 图中深色部分表示用户请 求（hq）所覆盖的区域。除了 LP条件外，其他IP条件相同的 hq可以标注在同一张图上。在积累了若干条hq后，就可以得到 图中的浅色区域，该区域代表了所需要预取的数据。 在实际的实现过程中，将 hq 表示为以下格式的四元组： 表名，选取字段列表，LP条件，IP条件?R 针对该四元组进行的算法描述如下： (1) 用相同表名和 IP 条件的四元组构成一个集合； (2) 从集合中得到LP条件的最大

9、和最小值； (3) 根据集合中所有的选取字段列表生成一个字段列表，该 列表包含所有在集合中出现过的字段； (4) 根据表名、IP条件、LP条件的最大/最小值以及包含所 有字段的列表构成一个新的四元组，并从该四元组生成预取指 令； (5) 执行预取指令，并缓存结果。 22 群体算法 群体算法是基于惯性规则思想实现的。 与蚁群算法一样， 该 算法也把 hq 表示为相同格式的四元组进行处理；与蚁群算法不 同的是， 群体算法并不是一个确定性的算法。 该算法利用具有前 向反馈功能的BP网络来记录历史hq，同时其输出的内容将取决 于用于训练的样本空间。该算法的具体流程如下： (1) 用相同表名的四元组构成

10、一个集合， 并按照接收 hq 的次 序为每个 hq 编号。 (2) 得到该表的所有字段， 并分别编号； 之后的所有处理 都使用编号来代替相应的字段 (3) 构造一个BP网络，其输入为hq编号、选取字段列表和 IP 条件；其输出为选取字段列表和 IP 条件。 (4) 训练时，若选取字段列表中包含某字段，则该字段对应 的输入为 1；否则为 0， IP 条件字段也作同样处理。 (5) BP 网络的评价函数通过将输出结果与训练集合中的下一 条 hq 对比得到。若某字段在选取字段列表的输出为 1, 而且在下 一条 hq 的选取字段中也存在，则认为输出正确；否则错误。 (6) 通过反复训练，直到训练结果收

11、敛或达到指定的正确率 为止。 (7) 当有新的 hq 到达时，将该 hq 分解为四元组，并将对应 的字段映射到指定的编号上，然后作为 BP网络的输入，用得到 的输出重新构建四元组及查询指令。 (8) 将得到的查询指令作为预取指令并执行，缓存结果。 3 预取性能分析 预取算法的主要目标就是利用历史知识来预测未来， 从而可 以有效地提高未来查询的响应速度。 其性能考查的指标主要包括 预取率和命中率。 预取率体现了预取算法占用系统资源的程度。 其中系统资源 包括计算资源和存储资源， 考虑到预取一般都发生在计算资源相 对空闲的时候， 因此可以不考虑计算资源对预取率的影响， 而仅 考虑存储资源对预取率的

12、影响。预取率计算公式为 其中， hitf 表示命中率； hits 表示每个 hq 在缓冲中的命中 次数； totals 表示每个 hq 分解的任务数 一般来说， 预取率比较低的算法其命中率也比较低。 这是因 为缓冲范围减小的原因， 可以通过计算不同预取率情况下的命中 率变化来找到一个最佳预取率， 使得小于该预取率时， 命中率变 化曲线比较快速； 当大于该预取率之后， 命中率变化曲线比较平 缓，则此预取率具有较高的性价比。 对于蚁群算法， 由于其具有明确的预取范围， 预取率一般是 可以预测的；对于群体算法，由于其不是一个确定性的算法，预 取率变化范围比较大。 但由于可以通过对网络参数的调整来得到

13、 不同的预取率， 可以根据上面提出的方法， 通过实际测试获取一 个比较合理的预取率。 4 实验结果分析 为了验证两种算法的效果，分别设计了两种实验方法。 （1）采用与 WangDazhi 类似的方法，即监控一个时段某个 应用访问数据库的所有查询语句， 并记录查询模版数量随时间变 化的曲线。在本实验中，选择某科学网格计算系统作为参考应用， 其结果如图 2 所示。 由图 2可以看出， 随着查询数据的增长， 查询模板的数量变 化很小。因此在此假设基础上实现的优化算法具有良好的预测能 力。 （2）模拟多应用场合下，在查询条件相对随机的情况下， 验证优化算法的预测效果。实验方法如下： 每个测试单元之间执行清除 Oracle 数据库自身 Cache 的 操作，避免Oracle的Cache干扰实验结果。？木?3是在记录规 模为 5.76 亿条的 Oracle 10g 数据库上执行全文查询的实验结 果。从实验结果可以看出，在查询返回记录增加到万条以上后， 查询速度有了明显提高。由于排除了 Oracle本身Cache的干扰， 可以认为查询效率的提高主要得益于预取算法发挥了效果。 5 结束语 对海量数据进行检索是一项非常耗时的操作， 通常采用预取 算法来对其进行优化以达到满足响应速度