一种数据库查询中最优执行计划的搜索方法

摘要

本发明涉及一种数据库查询中最优执行计划的搜索方法，包括在执行计划的搜索过程中不予考虑含有笛卡尔积连接操作的执行计划(除非用户提交的查询语句中含有笛卡尔积连接操作)，同时将语句中的关系表的连接关系以一个图的形式表示，最后在图中搜索最优执行计划；所述以图的形式表示语句的连接关系如下：图中的点表示查询语句中的关系，如果图中某两个点所对应的关系有连接操作(包括内连接和外连接)，则连接这两点，边的权值为两关系连接操作的执行代价。本发明由于采用了上述结构，可以在并行执行环境下得出最优执行计划。

主权项

1.一种数据库查询中最优执行计划的搜索方法，其特征在于，所述方法包括在执行计划的搜索过程中不予考虑含有笛卡尔积连接操作的执行计划，除非用户提交的查询语句中含有笛卡尔积连接操作，同时将语句中的关系表的连接关系以一个图的形式表示，最后在图中搜索最优执行计划；所述以图的形式表示语句的连接关系如下：图中的节点表示查询语句中的关系表，如果图中某两个节点所对应的关系表有连接操作，该连接操作包括内连接和外连接，则连接这两点，边的权值为两关系表连接操作的执行代价；所述在图中搜索最优执行计划的方案包含如下一些步骤：步骤一：从图中任一节点出发，在图中找出一条以该节点为起始点的连接通路，该连接通路对应原查询语句的一个执行计划，同时使得该执行计划为从该节点出发所对应的代价最小的执行计划；具体包括以下一些步骤：a、计算图中与该节点相关的所有边的权值；b、将计算得到的权值最小的边作为连接通路的第一条边；c、用新的节点替换第一条边，重新计算与该点相关的边的权值；d、将计算得到的权值最小的边作为连接通路的第二条边；e、依次下去直到遍历完图中所有的点；步骤二：依次从图中其它各节点出发，同样得出以这些节点为起始点的连接通路，使得该连接通路所对应的执行计划的代价最小；步骤三：比较前两步得出的所有连接通路所对应的执行计划的代价，得出代价最小的连接通路；步骤四：得出代价最小的连接通路后，采用自定义的动态分配方案将该通路中各个连接操作分配到各线程执行；步骤如下：假设最优执行计划所对应的连接通路中有n个操作，有m个线程并行执行；a)将连接通路中前m个操作分别在m个线程中执行，并记录m个线程中执行时间最短的线程；b)将连接通路中下一个操作直接投放到执行时间最短的线程，并重新更新线程池中执行时间最短的线程；c)如果连接通路中还有操作未执行则执行步骤b)；所述计算边的权值即计算边所对应的连接操作的执行时间，具体方案如下：若通过关系表的索引信息访问该关系表中一条记录的平均时间为通过嵌套循环访问关系表中一条记录的平均时间为对关系表建立临时索引时每个元组消耗的平均时间为对于某一连接操作关系表R₁和R₂的元组个数分别为N₁，N₂；如果R₁上建有相应的索引且R₂上没有建立索引，则该操作的时间开销为$T=\min (N_2*{\bar{T}}_i,N_1*N_2*{\bar{T}}_c);$如果R₂上建有相应索引且R₁上没有建立相关索引，则该操作的时间开销为$T=\min (N_1*{\bar{T}}_i,N_1*N_2*{\bar{T}}_c);$如果R₁和R₂上均建有相关索引，则该操作的时间开销为$T=\min (N_2*{\bar{T}}_i,$$N_1*{\bar{T}}_i,N_1*N_2*{\bar{T}}_c);$如果R₁和R₂上都没有相关索引，在对R₁和R₂都没有进行预处理的情况下执行时间为现在通过建立临时索引的方式执行上述操作，若对R₁建立临时索引，则执行时间为若对R₂建立临时索引，则执行时间为故在关系表R₁和R₂都没有索引的情况下的执行时间代价为$T=\min (N_1*N_2*{\bar{T}}_c,N_1*{\bar{T}}_t+N_2*{\bar{T}}_i,N_2*{\bar{T}}_t+N_1*{\bar{T}}_i).$