执行计划生成(数据库)
时间：2022-12-07 10:30:01 | 来源：信息时代
时间：2022-12-07 10:30:01 来源：信息时代
执行计划生成 : DBMS为用户的查询请求生成执行计划的过程,是DBMS查询优化器的主要任务。一个查询的执行计划确定了DBMS查询执行引擎执行该查询的方式。
为生成高效的执行计划,查询优化器一方面要合理选择单个操作符的操作算法,确定需要的缓冲区大小,以及选择满足交换律和结合律的操作符的操作顺序等,同时还需要考虑整个查询树的执行方式和执行顺序,主要包括父子结点间传递中间结果的方式和计划树的执行顺序。
子结点向父结点传递中间结果可能是以实体化方式,也可能是以流水线方式。当内存不足时,或父子操作符之间存在天然的阻塞关系时,子结点需要以实体化方式向父结点传递中间结果,即子结点的输出结果将以临时文件形式写到磁盘上,父结点必须在子结点执行结束后才可以开始执行,并去磁盘上读取子结点产生的输出数据作为其输入。子结点以流水线方式向父结点传递中间结果时,子结点操作符的输出将写到内存缓冲区中,父结点操作符从缓冲区读数据,父子操作符可以并行执行,而不必等待子操作符执行结束。
例如, 对于关系代数操作:πA.B(σR.C<10(R⋈S)),其对应的查询计划树如图1所示。
图1 查询计划树示例
当采用实体化方法时,从计划树的最底层操作符开始,即对关系R做选择操作,并将中间结果存储在临时关系T
1中。然后执行树的高一层操作,即连接操作,连接操作的一个输入来自前面建立的临时关系T
1,另一个输入来自数据库表S,连接结果将再次写入临时关系T
2。最后计算根结点的运算,即投影运算,其输入来自连接操作产生的临时关系T
2,之后得到最终结果。在实体化方法中,每个操作的中间结果将实体化为一个临时关系,写到磁盘上去,以其作为输入的高一层操作再到磁盘上将该临时关系读到内存,因此I/O代价比较高。
当采用流水线方法时,选择操作的输出放在内存中,当选择操作产生了一个或多个数据块时,就可以开始连接操作。当关系S全部与这些块匹配后,这些中间结果就可以丢弃。选择操作可以接着再产生一块或多块输出。连接操作生成的结果也不需要写入外存,而是直接投影输出。
当确定了父子操作间传递数据的方式后,查询执行器需要将查询执行计划树按照父子结点间的实体化关系,以前序遍历的顺序将计划树分成若干棵子树,并按此顺序依次执行各子树。每个子树内部的各结点可以按流水线方式同时执行,子树之间按实体化方式顺序执行。最后根结点的输出即是得到的最终查询结果。
例如,对于图2的查询计划,假设各个表都比较大,无法放入内存,需要采用两趟Hash Join算法进行连接,即第一趟将要连接的外表和内表按照连接属性的Hash值分成n个可独立连接对,然后在第二趟分别对n个可独立连接对进行连接。这时各个连接操作符之间必须以实体化的方式执行。不严格地说,该查询计划被划分成如图3所示的三棵子树,查询执行器将按从左至右的顺序执行这些子树,而每一棵子树的执行均采用流水线方式。
图2 多表连接的查询计划树示例
图3 分解后的查询计划树
在线咨询
