流水线相关树查询优化器和调度器

摘要

本发明实施例提供了一种方法，包括：遍历具有多个节点的查询计划树，每个节点表示对查询的主题数据进行的操作，从而从查询计划树中提取多个流水线，识别所述提取的多个流水线之间的相关性，并根据所述提取的多个流水线之间的相关性来提供流水线相关树，以便由多个处理器进行查询。

权利要求

1.一种方法，其特征在于，包括：

一个或多个处理器从具有多个节点并存储在存储器中的查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；

识别所述提取的多个流水线之间的相关性；

根据所述提取的多个流水线之间的相关性生成流水线相关树，以便由多个处理器进行所述每个流水线中的节点序列表示的操作；

其中，所述遍历所述查询计划树包括：

通过所述查询计划树的节点发起节点堆栈，包括根节点；

发起流水线堆栈；

确定所述节点堆栈中的当前节点是否为流水线断裂节点。

2.根据权利要求1所述的方法，其特征在于，所述遍历所述查询计划树包括：从根节点开始，使用所述查询计划树的迭代后序遍历对所述每个节点进行仅一次访问。

3.根据权利要求1所述的方法，其特征在于，如果所述当前节点不是流水线断裂节点，将所述当前节点附加到所述流水线堆栈中的当前流水线中。

4.根据权利要求1所述的方法，其特征在于，所述遍历所述查询计划树还包括：如果所述当前节点是流水线断裂节点，则确定所述当前节点是否为连接节点，如果不是连接节点，则将所述当前节点附加到所述流水线堆栈中的当前流水线，在所述流水线堆栈中发起新流水线，并指定所述当前流水线和所述新流水线之间的父子关系。

5.根据权利要求1所述的方法，其特征在于，还包括：

调度所述多个流水线以在多个处理器上并行执行；

根据所述调度在所述多个处理器上执行所述多个流水线。

6.根据权利要求5所述的方法，其特征在于，所述并行执行的多个流水线包括独立的流水线，其中，父流水线为第一级流水线，所述父流水线的子流水线为第二级流水线，所述独立的流水线为同一级别的子流水线。

7.根据权利要求6所述的方法，其特征在于，在不违反流水线之间的数据相关性的前提下根据父流水线的最少等待时间调度所述多个流水线运行在多个处理器上。

8.根据权利要求5所述的方法，其特征在于，根据一个函数调度运行所述多个流水线，所述函数在不超过一个主机的计算资源的同时，将跨主机资源的流水线执行时间重叠最大化。

9.根据权利要求5所述的方法，其特征在于，根据一个函数调度运行所述多个流水线，所述函数用于在不违反资源约束并避免不必要的数据重组的条件下进行局部感知调度。

10.一种设备，其特征在于，包括：

包含指令的非瞬时性内存存储器；以及与所述内存存储器通信的一个或多个处理器，其中，所述一个或多个处理器执行所述指令以遍历具有多个节点的查询计划树，每个节点表示对查询的主题数据进行的操作，以进行以下步骤：从具有多个节点并存储在存储器中的查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，通过遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；

识别所述提取的多个流水线之间的相关性；

根据所述提取的多个流水线之间的相关性生成流水线相关树，以便由多个处理器进行所述每个流水线中的节点序列表示的操作；

其中，所述遍历所述查询计划树包括：

通过所述查询计划树的节点发起节点堆栈，包括根节点；

发起流水线堆栈；

确定所述节点堆栈中的当前节点是否为流水线断裂节点。

11.根据权利要求10所述的设备，其特征在于，所述遍历所述查询计划树包括：从根节点开始，使用所述查询计划树的迭代后序遍历对每个节点进行仅一次访问。

12.根据权利要求10所述的设备，其特征在于，所述遍历所述查询计划树还包括：如果所述当前节点不是流水线断裂节点，则将所述当前节点附加到所述流水线堆栈中的当前流水线中；如果所述当前节点是流水线断裂节点，确定所述当前节点是否为连接节点，如果不是连接节点，则将所述当前节点附加到所述流水线堆栈中的当前流水线，在流水线堆栈中发起新流水线，并指定所述当前流水线和所述新流水线间的父子关系。

13.根据权利要求10所述的设备，其特征在于，还包括：

调度所述多个流水线以在多个处理器上并行执行，其中，所述并行运行的多个流水线包括独立的流水线，父流水线为第一级流水线，所述父流水线的子流水线为第二级流水线，所述独立的流水线为同一级别的子流水线；

根据所述调度在所述多个处理器上执行所述多个流水线。

14.根据权利要求13所述的设备，其特征在于，在不违反流水线之间的数据相关性的前提下根据父流水线的最少等待时间调度所述多个流水线运行在多个处理器上。

15.根据权利要求14所述的设备，其特征在于，根据一个函数调度运行所述多个流水线，所述函数在不超过一个主机的计算资源的同时，将跨主机资源的流水线执行时间重叠最大化；根据一个函数调度运行所述多个流水线，所述函数用于在不违反资源约束并避免不必要的数据重组的条件下进行局部感知调度。

16.一种存储计算机指令的非瞬时性计算机可读介质，其特征在于，所述计算机指令在由一个或多个处理器执行时使所述一个或多个处理器执行以下步骤：遍历具有多个节点的查询计划树，其中，每个节点表示对查询的主题数据进行的操作，来进行以下步骤：从所述查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，通过遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；

识别所述提取的多个流水线之间的相关性；

根据所述提取的多个流水线之间的相关性来提供流水线相关树，以便由多个处理器进行查询；其中，所述遍历所述查询计划树包括：通过所述查询计划树的节点发起节点堆栈，包括根节点；

发起流水线堆栈；

确定所述节点堆栈中的当前节点是否为流水线断裂节点。

17.根据权利要求16所述的非瞬时性计算机可读介质，其特征在于，所述遍历所述查询计划树包括：使用所述查询计划树的迭代后序遍历对每个节点进行仅一次访问。

18.根据权利要求16所述的非瞬时性计算机可读介质，其特征在于，所述遍历所述查询计划树还包括：如果所述当前节点不是流水线断裂节点，则将所述当前节点附加到当前流水线中；如果所述当前节点为流水线断裂节点，确定所述当前节点是否为连接节点，如果不是连接节点，则将所述当前节点附加到当前流水线，发起新流水线，并指定所述当前流水线和所述新流水线间的父子关系。

19.根据权利要求16所述的非瞬时性计算机可读介质，其特征在于，还包括：调度所述多个流水线以在多个处理器上并行运行，其中，所述并行运行的多个流水线包括独立的流水线，父流水线为第一级流水线，所述父流水线的子流水线为第二级流水线，所述独立的流水线为同一级别的子流水线；

其中，在不违反流水线之间的数据相关性的前提下根据父流水线的最少等待时间调度所述多个流水线运行在多个处理器上；

根据一个函数调度运行所述多个流水线，所述函数在不超过一个主机的计算资源的同时，将跨主机资源的流水线执行时间重叠最大化；

根据一个函数调度运行所述多个流水线，所述函数用于在不违反资源约束并避免不必要的数据重组的条件下进行局部感知调度。

说明书

流水线相关树查询优化器和调度器

[0001] 相关申请案交叉申请

[0002] 本申请要求于2016年9月23日递交的发明名称为“流水线相关树查询优化器和调度器”的第15/274,681号美国申请案的在先申请优先权，该在先申请的内容以引入的方式并入本文。

技术领域

[0003] 本发明涉及查询优化器，具体涉及具备高流水线间并行性的流水线相关树查询优化器。

背景技术

[0004] 传统查询处理引擎表示通过计划节点树进行的查询计划，称为查询计划树。计划节点封装了用于执行查询的单个操作。节点排列为树状，中间结果从树的底部或叶子流向顶部。每个节点都有零个或多个子节点。一个子节点的输出用作父节点的输入。例如，一个连接节点有两个子节点，表示两个连接关系，而一个排序节点有单个表示要排序的输入的子节点。树的叶子是节点，能通过扫描(例如进行索引扫描或顺序全表扫描)存储的数据产生结果。

[0005] 查询计划树包括多个节点，这些节点包括用作迭代器的运算符。迭代器通常遵循打开-下一个-关闭(open-next-close)协议。在“火山式”的查询处理引擎中，使用此类查询计划树可能导致对应于正被使用的每一行的操作符的数量的许多虚拟函数调用。可能导致大量的内存加载和存储，并消耗大量资源和时间来进行查询。

[0006] 另一种类型的查询处理引擎通过及时编译生成执行查询的代码。运算符融合在一个被称为流水线的执行单元中，该流水线被编译为单个函数。代码生成指的是创建本地代码而不是解释代码。此类融合执行单元缺乏成本信息，难以进行优化，查询处理严格按照自下而上的方式进行，限制了执行方式。

发明内容

[0007] 本发明实施例提供了一种方法，包括：一个或多个处理器从具有多个节点并存储在存储器中的查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；识别所述提取的多个流水线之间的相关性；根据所述多个提取的流水线之间的相关性生成流水线相关树，以便由多个处理器进行所述每个流水线中的节点序列表示的操作。

[0008] 本发明实施例提供了一种设备，包括包含指令的非瞬时性内存存储器以及与内存存储器通信的一个或多个处理器。所述一个或多个处理器执行所述指令以遍历具有多个节点的查询计划树，每个节点表示对查询的主题数据进行的操作，以进行以下步骤：从具有多个节点并存储在存储器中的查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，通过遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；识别所述提取的多个流水线之间的相关性；根据所述多个提取的流水线之间的相关性生成流水线相关树，以便由多个处理器进行所述每个流水线中的节点序列表示的操作。

[0009] 本发明实施例提供了一种存储计算机指令的非瞬时性计算机可读介质。所述计算机指令在由一个或多个处理器执行时使所述一个或多个处理器执行以下步骤：遍历具有多个节点的查询计划树，其中，每个节点表示对查询的主题数据进行的操作，来进行以下步骤：从所述查询计划树中提取多个流水线；识别所述提取的多个流水线之间的相关性；根据所述提取的多个流水线之间的相关性来提供流水线相关树，以便由多个处理器进行查询。

附图说明

[0010] 图1为一示例实施例提供的生成用于查询的流水线相关树的流程框图；

[0011] 图2为一示例实施例提供的生成流水线相关树的方法的流程图；

[0012] 图3为一示例实施例提供的可由数据库系统生成的示例性查询计划树的示图；

[0013] 图4为一示例实施例提供的可以从图3的树生成的多个流水线的框图；

[0014] 图5为一示例实施例提供的结果流水线相关树的框图；

[0015] 图6为一示例实施例提供的遍历查询计划树以生成流水线相关树的方法的流程图；

[0016] 图7为一示例实施例提供的将成本模型应用于流水线相关树(pipeline dependent tree，简称PDT)的流程框图；

[0017] 图8为一示例实施例提供的示例性PDT和最后获得有向无环图(directed acyclic graph，简称DAG)的流程框图800；

[0018] 图9为一示例实施例提供的基于可替代的最小等待时间的调度方法的示图；

[0019] 图10为一示例实施例提供的基于可替代的最小等待时间的调度方法的示图；

[0020] 图11为示例实施例提供的针对客户端、服务器、基于云的资源的用于实现算法和执行方法的的电路的框图。

具体实施方式

[0021] 以下结合附图进行描述所述附图是描述的一部分并通过图解说明的方式示出可以实施本发明的具体实施例。这些实施例将充分详细描述使本领域技术人员能够实施本发明而且应该明白的是可以使用其它实施例并且在不脱离本发明的范围的情况下可以做出结构上、逻辑上、电学上的改变。因此以下示例实施例的描述并不当作限定，本发明的范围由所附权利要求书界定。

[0022] 本文描述的函数或算法可以在一实施例中的软件中实施。该软件可包含计算机可执行指令，这些计算机可执行指令存储在计算机可读介质上或者计算机可读存储设备上，如一个或多个非瞬时性存储器或其它类型的本地或联网的硬件存储设备。此外，这些函数对应模块，这些模块可以是软件、硬件、固件或其任意组合。多个函数可根据需要在一个或多个模块中执行，所描述的实施例仅为示例。该软件可在数字信号处理器、ASIC、微处理器上执行或者在个人计算机、服务器、或其它计算机系统等其它类型的计算机系统上运行的处理器上执行，从而将这些计算机系统转换成一个专门编程的机器。

[0023] 可由具有复数代数表达式的计划树表示查询。该树包含多个节点，其中，每个节点都是一个运算符。在现有查询处理方法中，计划树可以将其运算符融合到称为流水线的执行单元中，然后将其编译为单个函数。由于流水线上缺乏成本信息，这种查询处理方法无法进行基于成本的并行调度的优化。

[0024] 在各种实施例中，计算机系统上实现的系统和方法生成可以利用来自接收到的查询计划树的多个流水线的流水线相关树，通过在流水线相关树上应用成本模型来优化查询处理，以高流水线间并行性调度流水线相关树的执行，实现了利用多个处理器的现代计算机处理单元架构的优势。

[0025] 可根据各种调度方法(例如基于最少等待时间的调度)在一个或多个处理器上调度多个流水线，其中，可调度流水线在不违反流水线之间的数据相关性的情况下运行。在一些实施例中，可以通过贪婪算法将每个流水线适配成几个组，例如多个多处理器主机。对流水线进行局部感知调度也可用于将两个或多个相关流水线所需数据的重组最小化。

[0026] 在各种实施例中，针对基于流水线的查询处理系统进行高效的流水线生成。可显著改进复杂分析处理的性能，并可将流水线生成和调度移植到现有的大规模分析处理中。

[0027] 图1为一示例实施例提供的生成用于查询的流水线相关树的流程框图100。在118将具有多个节点115的查询计划树110输入到流水线相关树(pipeline dependent tree，简称PDT)生成器120。流水线相关树生成器120遍历查询计划树110并标识在125、130和135指示的多个流水线P1、P2和P3。生成输出140并提供给一个或多个主机的一个或多个处理器执行操作。输出130中，125的P1和130的P2为135的P3的子节点。流水线相关树的简单执行可包括单独的处理器并行地进行P1和P2并将结果提供给单个处理器以进行P3。

[0028] 在一个实施例中，遍历查询计划树使用查询计划树的迭代后序遍历对每个节点进行仅一次访问。这允许在无需硬编码流水线的情况下从任何查询中生成流水线相关树。

[0029] 图2是一示例实施例提供的生成流水线相关树的方法200的流程图。方法200包括在210获得查询计划树。查询计划树具有多个节点，每个节点表示对查询的主题数据进行的操作。在215遍历查询计划树，以从220的查询计划树中提取多个流水线，并在225标识多个提取的流水线之间的相关性，以及在230根据多个提取的流水线之间的相关性提供流水线相关树，以便由多个处理器进行查询。

[0030] 讨论简单查询、对应查询计划树、流水线识别，以及与简单查询对应的流水线树生成之后，下面还详细提供这些操作中的每一个操作的细节。

[0031] 在各种实施例中，可从用户或自动化报告或其它来源获得查询。一个示例查询(如结构化语言查询(structured language query，简称SQL))用于说明流水线树的生成：

[0032] SELECT y1.c1as c1,t2.c2 as c2

[0033] FROM tab1t1,tab2 t2,tab3 t3

[0034] WHERE t1.c0＝t2.c0and t2.c1＝t3.c1 and t1.c2＝5

[0035] “tab”和“t”指数据库中的表格，“c”指相应表格中的各个列。

[0036] 图3中的300示出了可以由数据库系统生成的查询计划树，可提供给执行方法200的操作的系统。这种查询计划树的生成在数据库系统中无处不在，并且可以通过许多不同的方式来生成。

[0037] 查询计划树300示出了与在执行查询计划树时要执行的节点相对应的若干操作，或者在现有系统中的这种树的成本优化版本。注意，树300的执行从下到上，先调度t1的扫描节点310，然后是315的项目节点c0、c1和c2，320的滤波器节点c2＝5，以及325的连接节点t1.c0＝t2.c0。在可以执行由连接节点325表示的连接之前，在330对t2进行扫描，并且在335对c0，c1的项目节点335进行调度。一旦对连接节点325进行调度，生成340的连接节点t2.c1＝t3.c1。首先，在扫描节点345扫描t3，并且在项目节点350确定c1。因此，树300表示可进行查询的操作。

[0038] 图4为可以从树300生成的多个流水线的框图。在一个实施例中，扫描节点330和项目节点335形成树的分支，该树具有JoinBuild节点t1.c0＝t2.c0的父节点410。该分支在415标识为流水线1(P1)。在420，第二分支包括扫描节点345，项目节点350和JoinBuild节点t1.c0＝t2.c0的父节点。该分支在425形成流水线2(P2)。另一分支包括扫描节点310，项目节点315，滤波器节点320，430的JoinProbe节点t1.c0＝t2.c0，以及435的JoinProbe节点t2.c1＝t3.c1的父节点，以形成440的流水线3(P3)。

[0039] 图5为结果流水线相关树500的框图，包括415的P1，425的P2，和440的P3。注意，操作从下往上进行，同一级别上的流水线可由不同处理器并行进行。

[0040] 图6为一示例实施例提供的遍历查询计划树以生成流水线相关树的方法600的流程图。在610根据查询计划树发起堆栈，包含节点堆栈和流水线堆栈。节点堆栈的根用于开始遍历。迭代的后序遍历确保查询计划树可以被访问一次。

[0041] 在613，决策块确定节点堆栈是否为空。若是，则在615完成流水线相关树的生成。若否，则在618将当前节点设置在节点堆栈的顶部。然后在620确定遍历是否正在进行。若是，则在622做出决策以确定当前节点是否具有子节点。若是，则在625将第一个子节点推送至节点堆栈，并返回至613以确定节点堆栈是否为空。如果没有找到子节点，则返回613。

[0042] 如果确定在620没有进行遍历，则在628确定当前节点是否为流水线断裂节点。若否，则在630将当前节点附加到当前流水线，并在632确定来自左侧子节点和当前节点的返回是否具有右侧子节点。若是，则节点堆栈在635推送当前节点的右侧子节点并返回至613。若否，则在638弹出节点堆栈并返回613。

[0043] 若当前节点在628是流水线断裂节点，则在640确定当前节点是否为连接节点。流水线断裂节点是由物化中间结果的必要性确定的。若当前节点不是连接节点，则将当前节点附加到当前流水线，认为当前流水线在642完整。发起新流水线实例，并且可以指定父子关系。然后在638弹出堆栈节点并返回613。

[0044] 若当前节点在640是连接节点，则决策块645确定来自树左侧的返回是否发生。若是，则在650将当前节点附加到当前流水线，将当前流水线推送到流水线堆栈stk_ppl，并在655确定连接是否建立在左侧。若连接建立在左侧，则在660将当前节点附加到当前流水线，弹出流水线堆栈，将弹出的元素分配给当前流水线的子节点，并返回613。若连接没有建立在左侧，则在665确定连接是否建立在右侧，若是，则将当前节点附加到当前流水线，将流水线弹出并分配给当前流水线的父节点，并返回613，若否，执行638，弹出节点堆栈。

[0045] 方法600对应的伪代码包括与图6一致的注释和标号，如下所示：

[0046] 初始化两个堆栈：stk_node stk_pipeline；/*这两个堆栈存储运算符节点和流水线，分别为*/

[0047] pre_node＝null/*最后访问的节点；和其父节点一同用于确定遍历方向。*/[0048] Pipeline＝empty/*当前处理的流水线*/

[0049] Push root node of execution plan to stk_node；--610

[0050] while(stk_node！＝null){--613

[0051] cur_node＝stk.node.top()；--618

[0052] if(goingDown)/*traverse top-down*/--620

[0053] if cur_node has children，push the first child to stk_node；--622,625[0054] else

[0055] if(cur_node isn’t pipeline breaker)--628

[0056] add cur_node to current pipeline--630

[0057] if(goingUp&&backtracked from left child node&&cur_node has right child node)--632

[0058] stk_node.push(cur_node.rightChild)；--635

[0059] else stk_node.pop()；--638

[0060] else

[0061] if(cur_node is join operator)--640

[0062] if(goingUp&&backtracked from left child node)--645

[0063] add cur_node to current pipeline；--650

[0064] stk_pipeline.push(pipeline)--650

[0065] pipeline＝new Pipeline()；--650

[0066] else if(buildside＝＝buildleft)--655

[0067] add cur_node  to current pipeline；stk_pipeline.pop()；current pipeline.Child＝popped element；--660

[0068] else if(buildside＝＝buildright)--665

[0069] add cur_node  to current pipeline；stk_pipeline.pop()；current pipeline.parent＝popped element；--660

[0070] the current pipeline is complete；--660

[0071] if(cur_node  has  right  child  node)--665stk_node.push(cur_node.rightChild)；

[0072] else stk_node.pop()；--638

[0073] else//other pipeline breakers；unaryNode；

[0074] add cur_node to current pipeline；current pipeline is complete；--670[0075] newpipeline＝new Pipeline()；pipeline.parent＝newpipeline；--670[0076] s pipeline＝newpipeline；stk_node.pop()--670

[0077] }//end while

[0078] 图7为一示例实施例提供的将成本模型应用于流水线相关树(pipeline dependent tree，简称PDT)的流程框图700。SQL查询在710接收，并且在715解析，以提供抽象语法树(abstract syntax tree，简称AST)。数据库引擎分析器720用于解析AST并将解析后的AST提供给优化器725。到目前为止进行的操作是常规的并生成如先前所示的查询计划树形式的最优计划。在现有数据库系统中，最优计划被提供给执行引擎730，以使用查询计划树进行查询。

[0079] 在本发明主题的一个实施例中，优化器725将查询计划树提供给遍历该查询计划树的PDT生成器735，以生成流水线相关树740形式的多个流水线。流水线相关树740被提供给成本模型745。成本模型用于计算基于成本的度量，例如输入流中的数据大小和行数，输出流中的数据大小和行数，计算资源方面的执行整个流水线的成本，例如内核(例如主机上的处理器)的数量，内存消耗，以及估计的完成查询的时间。

[0080] 可在750将具有由成本模型提供的统计量的PDT提供给调度器755。调度器755可以在760查询处提供最优的有向无环图(directed acyclic graph，简称DAG)，可利用多个流水线和资源通过执行引擎730进行查询。在各种实施例中，调度器755可以根据各种不同的目标生成DAG。

[0081] 图8为示出示例性PDT并得到DAG的流程框图800。PDT示为节点树，包括810的流水线P1、815的流水线P2、820的流水线P3和825的流水线P4。一般地，830指示DAG，P1、P2和P3同在级别2，P4在级别1，用作父节点。因此，P1，P2和P3是P4的子流水线并且互为兄弟流水线。P1，P2和P3是独立的流水线，每个流水线为相同的从属级别2。作为独立的流水线，可调度P1，P2和P3以并行的方式运行，这最适合利用多个CPU内核的现代中央处理器(central processing unit，简称CPU)架构。

[0082] 在一个实施例中，可基于最少的等待时间调度流水线。父流水线需等待所有子流水线执行完成后执行。目的是最小化父流水线的总等待时间，然后才能调度子流水线在不违反流水线间的数据相关性的情况下运行。在传统的查询处理系统中，将按照以下顺序执行流水线：P1→P2→P3→P4，总进行时间为T(P1)+T(P2)+T(P3)+T(P4)。然而，在有足够可用资源的最佳情况下，可基于最少等待时间调度P1、P2和P3以并行的方式运行，使得执行时间为T(P4)+Max(T(P1),T(P2),T(P3))。P4只需等待较低级别的流水线的最长执行时间，这大大少于传统的连续进行时间。

[0083] 图9为基于可替代的最小等待时间的调度方法900的示图。给定总的可用计算资源矢量为RA[]，估计的流水线执行时间矢量为T[]。可以通过流水线RR[]的计算资源矢量使用贪婪算法将其中的每个流水线适配至一些(#of hosts)组中。在用于执行操作的对应资源的表格905中示出了每个流水线，包括910的P1、915的P2和920的P3。在表905中，通过成本模型745为每个流水线提供了存储器，多个内核以及执行时间。在每个组中，需求计算资源的总和不超过可用资源。流水线执行时间的重叠可在不同的组最大化。

[0084] 资源表940示出两个主机：主机1和主机2，以及它们的存储器资源以及内核的数量，在两种情况下恰好都为10。可从表格905注意到，执行P2花费的时间最长。图950示出在执行P2的时间T(P2)期间使用相同的资源(任一主机上可用的10个内核中的4个)连续执行P1和P3，执行时间为T(P1)+T(P3)。使得能够通过调度器755在同时在主机1上调度P2以及在主机2上调度P1和P3。注意，通过确定在执行最长时间流水线的同时可连续执行三个流水线中的另两个流水线，则不需要第三个主机便可在最短的时间内进行查询。在这个例子中，可在T(P2)的总时间内执行同一级别上的三个流水线。

[0085] 图10为基于可替代的最小等待时间的调度方法1000的图示。给定总的可用计算资源矢量为RA[]，估计的流水线执行时间矢量为T[]。可以通过流水线RR[]的计算资源矢量使用贪婪算法将其中的每个流水线适配至一些(#of hosts)组中。在用于执行操作的对应资源的表格1005中示出了每个流水线，包括1010的P1、1015的P2和1020的P3。在表1005中，通过成本模型745为每个流水线提供了存储器，多个内核以及执行时间。在主机1上调度P2。资源表1040示出了两个主机：主机1和主机2，两个主机的存储器资源，以及其内核的数量，在两种情况下都恰好为10。在主机2上调度P1和P3。

[0086] 图1050示出在执行P2的时间T(P2)期间使用相同的资源(任一主机上可用的10个内核)连续执行P1和P3，执行时间为T(P1)+T(P3)。使得能够同时在主机1上调度P2以及在主机2上调度P1和P3。注意，P1使用表1005中的5个内核，P3使用表1005中的6个内核。由于主机2只有10个内核的资源，因此P1和P2不能在主机2上同时运行。但是，即便在P1之后运行P3，总执行时间仍然低于P2的执行时间。

[0087] 在另一个实施例中，参照图8，可以利用流水线的局部感知调度。在某些查询中，可能需要将中间结果物化。换句话说，可能需要进行一些计算来提供所需信息。这种物化可能导致流水线断裂。可能需要在流水线之间共享数据，然后才能继续处理。通常，数据共享可称为数据重组，可针对两个相关流水线进行。

[0088] 在一个示例中，若在不同的主机上调度P1、P2和P3，则数据重组可以发生在P1与P4、P2与P4以及P3与P4之间。这可能导致最多2+2+2＝6次重组。若在不同的主机联网时需要重组，网络延迟可能会显著增加查询执行时间。局部感知调度可用于在不违反资源限制的情况下为同一主机调度尽可能多的兄弟流水线。同一主机中的内核可共享内存并避免进行重组，或者至少相当快地进行重组，因此可以显著减少重组。在一个实施例中，在不违反可用计算资源的数据相关性或约束的前提下，可将局部感知调度用作对最少等待时间调度的启发式补充。

[0089] 在利用相同示例的另一个实施例中，属于同一分区的所有中间结果都在一个主机(例如主机1)上进行调度。如图9所示，可以在一个主机上调度P1、P2和P3，既没有违反内存约束也没有违反内核可用性。P2和P1可使用10个可用内核中的7个以同时运行，并且可以在P1完成后发起P3。当发起P4来探测P1、P2和P3时，重组次数可以减少到4次(P1一次、P2一次、P3一次和P4一次)。

[0090] 图11为示例实施例提供的用于实现数据库系统的电路的框图，该数据库系统用于生成并执行来自查询计划树的流水线相关树，以实现算法并执行方法。在各种实施例中无需使用所有的组件。例如，客户端、服务器和基于云的网络资源可以分别使用不同组的组件，或者例如在服务器的情况下，使用较大的存储设备。

[0091] 计算机1100形式的一个示例计算设备可以包括处理单元1102，存储器1103，可移动存储器1110，以及不可移动存储器1112。虽然该示例计算设备被图示和描述为计算机1100，但是在不同的实施例中该计算设备可以为不同的形式。例如，该计算设备可以为智能手机，平板电脑，智能手表或其它包括如图11所示和描述的相同或相似的元件的计算设备。
智能手机，平板电脑和智能手表等设备通常统称为移动设备或用户设备。此外，虽然各种数据存储元件被图示为计算机1100的一部分，但是该存储器还可以或者可替代地包括可借助网络(例如互联网或基于服务器的存储器)进行访问的基于云的存储器。

[0092] 所述存储器1103可包括易失性存储器1114和非易失性存储器1108。所述计算机1100可包括或访问计算环境。该计算环境包括各种计算机可读介质，如易失性存储器1114和非易失性存储器1108、可移动存储器1110和不可移动存储器1112。计算机存储器包括随机存取存储器(random access memory，简称RAM)、只读存储器(read-only memory，简称ROM)、可擦除可编程只读存储器(erasable programmable read only memory，简称EPROM)和电可擦除可编程只读存储器(electrically erasable programmable read-only memory，简称EEPROM)、闪存或其它存储器技术、只读光盘(compact disc read-only memory，简称CD ROM)、数字多功能光盘(digital versatile disc，简称DVD)或其它光盘存储器、盒式磁带、磁带、磁盘存储器或其它磁存储设备，或者任何其它能够存储计算机可读指令的介质。

[0093] 计算机1100可以包括或者可以访问包括输入1106，输出1104和通信连接1116的计算环境。输出1104可以包括也可以用作输入设备的显示设备，例如触摸屏。输入1106可以包括一个或多个触摸屏、触摸板、鼠标、键盘、摄像头、一个或多个设备专用按钮，一个或多个集成在计算机1100内或通过有线或无线数据连接耦合到计算机1100的传感器，以及其它输入设备。计算机可以在联网环境中利用通信连接运行以连接到一个或多个远程计算机，例如数据库服务器。远程计算机可以包括个人计算机(personal computer，简称PC)、服务器、路由器、网络PC、对等设备或其它公共网络节点等。通信连接可以包括局域网(local area network，简称LAN)、广域网(wide area network，简称WAN)、蜂窝、WiFi、蓝牙或其它网络。存储在计算机可读介质上的计算机可读指令可由计算机1100的处理单元1102执行。硬盘驱动器、CD-ROM和RAM是产品的一些示例，所述产品包括非瞬时性计算机可读介质，如存储设备。若认为载波过于短暂，则术语“计算机可读介质”和“存储设备”不包括载波。

[0094] 示例如下：

[0095] 1、在示例1中，方法包括：一个或多个处理器从具有多个节点并存储在存储器中的查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；识别所述提取的多个流水线之间的相关性；根据所述多个提取的流水线之间的相关性生成流水线相关树，以便由多个处理器进行所述每个流水线中的节点序列表示的操作。

[0096] 2、在示例1的方法中，所述遍历所述查询计划树包括：从根节点开始，使用所述查询计划树的迭代后序遍历对所述每个节点进行仅一次访问。

[0097] 3、在示例2的方法中，所述遍历所述查询计划树包括：通过所述查询计划树的节点发起节点堆栈，包括根节点；发起流水线堆栈；确定所述节点堆栈中的当前节点是否为流水线断裂节点。

[0098] 4、在示例3的方法中，如果所述当前节点不是流水线断裂节点，将所述当前节点附加到所述流水线堆栈中的当前流水线中。

[0099] 5、在示例3的方法中，所述遍历所述查询计划树还包括：如果所述当前节点是流水线断裂节点，则确定所述当前节点是否为连接节点，如果不是连接节点，则将所述当前节点附加到所述流水线堆栈中的当前流水线，在所述流水线堆栈中发起新流水线，并指定所述当前流水线和所述新流水线之间的父子关系。

[0100] 6、示例1的方法还包括：调度所述多个流水线以在多个处理器上并行执行；根据所述调度在所述多个处理器上执行所述多个流水线。

[0101] 7、在示例6的方法中，所述并行执行的多个流水线包括独立的流水线，其中，父流水线为第一级流水线，所述父流水线的子流水线为第二级流水线，所述独立的流水线为同一级别的子流水线。

[0102] 8、在示例7的方法中，在不违反流水线之间的数据相关性的前提下根据父流水线的最少等待时间调度所述多个流水线运行在多个处理器上。

[0103] 9、在示例6的方法中，根据一个函数调度运行所述多个流水线，所述函数在不超过一个主机的计算资源的同时，将跨主机资源的流水线执行时间重叠最大化。

[0104] 10、在示例6的方法中，根据一个函数调度运行所述多个流水线，所述函数用于在不违反资源约束并避免不必要的数据重组的条件下进行局部感知调度。

[0105] 11、在示例11中，设备包括包含指令的非瞬时性内存存储器；以及与所述内存存储器通信的一个或多个处理器。所述一个或多个处理器执行所述指令以遍历具有多个节点的查询计划树，每个节点表示对查询的主题数据进行的操作，以进行以下步骤：从具有多个节点并存储在存储器中的查询计划树中提取多个流水线，其中，每个节点表示对查询的主题数据进行的操作，通过遍历所述查询计划树来识别每个流水线的节点序列，并启动新流水线作为流水线断裂节点的函数，所述流水线断裂节点根据对应于一个节点，表示将中间结果进行物化的操作；识别所述提取的多个流水线之间的相关性；根据所述提取的多个流水线之间的相关性生成流水线相关树，以便由多个处理器进行所述每个流水线中的节点序列表示的操作。

[0106] 12、在示例11的设备中，所述遍历所述查询计划树包括：从根节点开始，使用所述查询计划树的迭代后序遍历对每个节点进行仅一次访问。

[0107] 13、在示例11的设备中，所述遍历所述查询计划树包括：通过所述查询计划树的节点发起节点堆栈，包括根节点；发起流水线堆栈；确定所述节点堆栈中的当前节点是否为流水线断裂节点，如果所述当前节点不是流水线断裂节点，则将所述当前节点附加到所述流水线堆栈中的当前流水线中；如果所述当前节点是流水线断裂节点，确定所述当前节点是否为连接节点，如果不是连接节点，则将所述当前节点附加到所述流水线堆栈中的当前流水线，在流水线堆栈中发起新流水线，并指定所述当前流水线和所述新流水线间的父子关系。

[0108] 14、示例11中的设备还包括：调度所述多个流水线以在多个处理器上并行运行，其中，所述并行运行的多个流水线包括独立的流水线，父流水线为第一级流水线，所述父流水线的子流水线为第二级流水线，所述独立的流水线为同一级别的子流水线；根据所述调度在所述多个处理器上执行所述多个流水线。

[0109] 15、在示例14的设备中，在不违反流水线之间的数据相关性的前提下根据父流水线的最少等待时间调度所述多个流水线运行在多个处理器上。

[0110] 16、在示例15的设备中，根据一个函数调度运行所述多个流水线，所述函数在不超过一个主机的计算资源的同时，将跨主机资源的流水线执行时间重叠最大化；根据一个函数调度运行所述多个流水线，所述函数用于在不违反资源约束并避免不必要的数据重组的条件下进行局部感知调度。

[0111] 17、示例17提供了一种存储计算机指令的非瞬时性计算机可读介质。计算机指令在由一个或多个处理器执行时使所述一个或多个处理器执行以下步骤：遍历具有多个节点的查询计划树，其中，每个节点表示对查询的主题数据进行的操作，来进行以下操作：从所述查询计划树中提取多个流水线；识别所述提取的多个流水线之间的相关性；根据所述提取的多个流水线之间的相关性来提供流水线相关树，以便由多个处理器进行查询。

[0112] 18、在示例17的非瞬时性计算机可读介质中，所述遍历所述查询计划树包括：使用所述查询计划树的迭代后序遍历对每个节点进行仅一次访问。

[0113] 19、在示例17的非瞬时性计算机可读介质中，所述遍历所述查询计划树包括：确定当前节点是否为流水线断裂节点，如果所述当前节点不是流水线断裂节点，则将所述当前节点附加到当前流水线中；如果所述当前节点为流水线断裂节点，确定所述当前节点是否为连接节点，如果不是连接节点，则将所述当前节点附加到当前流水线，发起新流水线，并指定所述当前流水线和所述新流水线间的父子关系。

[0114] 20、示例17的非瞬时性计算机可读介质还包括：调度所述多个流水线以在多个处理器上并行运行，其中，所述并行运行的多个流水线包括独立的流水线，父流水线为第一级流水线，所述父流水线的子流水线为第二级流水线，所述独立的流水线为同一级别的子流水线；其中，在不违反流水线之间的数据相关性的前提下根据父流水线的最少等待时间调度所述多个流水线运行在多个处理器上；根据一个函数调度运行所述多个流水线，所述函数在不超过一个主机的计算资源的同时，将跨主机资源的流水线执行时间重叠最大化；根据一个函数调度运行所述多个流水线，所述函数用于在不违反资源约束并避免不必要的数据重组的条件下进行局部感知调度。

[0115] 虽然上文详细描述了几个实施例但是可能进行其它修改。例如为了获得期望的结果附图中描绘的逻辑流不需要按照所示的特定顺序或者先后顺序。可以提供其它步骤或者从所描述的流程中去除步骤，所描述的系统中可以添加或移除其它组件。其它实施例可以在所附权利要求书的范围内。