SQL服务器中的多步骤查询执行

摘要

提供了在数据库应用中构造和执行多步骤查询计划的方法、系统和计算机程序产品。数据库应用接受查询，诸如例如图查询。数据库应用生成物理查询计划，该物理查询计划包括执行查询的执行步骤集。该执行步骤集至少包括初始步骤、中间步骤和最终步骤。数据库通过将控制传递给初始步骤来执行查询，当初始步骤完成时将执行控制传递给某一其他步骤。中间步骤执行并且当完成时，可以将执行控制传递给任何其他步骤，包括它自身。步骤可以被配置为在步骤之间传送任意数据。所生成的查询计划还可以包括多个多步骤序列，并且这样的序列可以被配置为基于中间查询结果或查询中包括的参数来交替地执行。

说明书

背景技术

现代数字世界正在经历与商务和个人生活的各个方面相关联的数据量的指数增长。迫切需要针对有效存储和召回这样的信息的解决方案。商务尤其需要将收集和存储的数据变换为可动作的情报。关系数据库系统以及被编写以利用这样的系统的应用是用于描述、存储和取回商务信息的传统工具。然而，最近，对图数据库系统的需求增加了。

代替关系数据库表的传统列和行，图数据库以节点和边的形式存储数据。节点表示不同的数据值或有关值的集合，并且边连接节点从而表示其间的关系。边可能同样具有一个或多个有关值(例如关系的持续时间)。例如，与公司雇员有关的数据可以由针对每个雇员的节点表示，并且边可以将彼此合作的雇员连接起来，从而表示合作者关系。在另一示例中，连接买方和产品的边可以表示产品购买，并且可以具有属性，诸如销售价格、数量、日期等。具有所有互连边的所有节点的完整图片被称为图。

在某些情形下，可能期望以图的形式(与本机关系数据库表相对)存储信息并执行图查询。例如，在商务应用或其基础数据涉及复杂的多对多关系时，或在需要对成为数据的基础的关系进行分析的任何时间(即在数据点之间的关系与数据点本身一样重要或更重要时)，可能期望图存储。在这些情况下，图存储和查询能力可能会很有用，因为图数据库系统通常允许人们更容易地表达某些类型的查询。例如，模式匹配、多跳导航、传递闭包和多态查询通常更易于利用图查询来表达。

越来越多地利用关系数据库系统来执行图数据库系统的功能。具体地，包括图的节点和边可以被存储在被称为节点和边表的普通关系表中。节点表存储与特定节点(例如雇员)有关的信息或参考，并且边表反映节点表中的节点之间的关系(例如合作者)。然而，关系数据库系统的这样的使用可以揭露某些问题。

例如，对关系数据库执行最短路径图查询需要重复递归地连接多个表，其中每个连接序列表示一个路径扩展。关系数据库系统通常本身不能执行这样的查询。为了执行这样的查询，可能迫使用户使用条件分支和临时存储来自定义制作查询，这可能带来显著的性能问题。同样，编写这样的条件逻辑容易出错，并且需要针对每个新查询的新代码。备选地，尽管这些递归公共表表达式(“CTE”)遭受性能问题的困扰，但它们可以被用于至少处置自定义查询的递归部分。此外，CTE的递归成员通常将递归直到没有行被返回为止，这意味着可能难以提前终止。

发明内容

提供本发明内容以按照简化形式介绍构思的选择，在下文具体实施方式中会进一步描述这些构思。本发明内容既不旨在标识所要求保护的主题的关键特征或本质特征，也不旨在被用于限制所要求保护的主题的范围。

方法、系统和计算机可读存储器设备被提供，其通过提供多步骤序列查询计划运算符来解决与关系数据库系统中的图查询和其他类型的查询的有效执行有关的问题。在一个方面中，数据库应用被配置为接受并处理查询以生成包括多步骤序列的查询计划，其中多步骤序列至少包括：初始步骤，被配置为执行并且将执行控制传递给另一步骤；中间步骤，被配置为执行并且将执行控制传递给另一步骤；以及最终步骤，被配置为执行以基于多步骤序列的上述步骤的执行结果来提供子查询结果。在一个方面中，子查询结果形成接收到的查询的结果的至少一部分基础。中间步骤可以包括递归步骤，该递归步骤被配置为生成递归步骤结果，并且经由递归将这样的结果传递回自身，除非提前终止条件被满足或直到提前终止条件被满足为止。

在一个方面中，关系数据库应用还可以生成针对查询计划的一个或多个附加的多步骤序列，并且确定要执行哪个多步骤序列。关系数据库应用可以至少部分地基于以下项来确定要执行哪个多步骤序列：查询计划的另一步骤的步骤结果、查询计划中的任何其他多步骤序列的中间查询结果、和/或对查询中所包括的可选参数的包括。

在另一个方面中，查询计划的多步骤序列可以包括如下步骤，该步骤被配置为以查询计划的相同或不同的多步骤序列将任意数据传送给一个或多个其他执行步骤。查询计划中的多步骤序列还可以包括多个子计划，这些子计划当被执行时各自生成相应的子计划结果，并且其中针对第一子计划的子计划结果可以被并入到另一子计划中，并且至少部分地形成该子计划的子计划结果的基础。此外，针对第一子计划的子计划结果可以被其他子计划或步骤重新使用，而无需重新执行第一子计划。

下文参考附图详细描述了实施例的其他特征和优点以及各个实施例的结构和操作。应注意，实施例不限于本文中所描述的特定实施例。本文中仅出于说明目的呈现这样的实施例。基于本文中所包含的教导，附加实施例对于(多个)有关领域的技术人员将是明显的。

附图说明

并入本文中并且形成说明书的一部分的附图图示了本申请的实施例，并且与描述一起还用以解释实施例的原理并使得有关领域的技术人员能够作出并使用实施例。

附图1示出了示例图，该图反映了工作者(节点)之间的合作者关系(边)。

附图2示出了示例关系数据库节点表，该示例关系数据库节点表描述了与附图1的图中所示出的节点相关联的特性。

附图3示出了示例关系数据库边表，该示例关系数据库边表描述了在附图1中示出且在附图2的节点表中反映的节点如何被连接。

附图4示出了可以被提交给示例实施例并且由示例实施例处理的示例图查询。

附图5示出了图示根据各种约束通过附图1的图的节点的可能遍历路径的表。

附图6示出了根据一个实施例的示例多步骤序列。

附图7示出了根据一个实施例的示例关系数据库系统的框图，该示例关系数据库系统包括多步骤查询计划生成器和多步骤查询计划执行器，多步骤查询计划生成器和多步骤查询计划执行器被配置为分别生成和执行包括多步骤序列的查询计划。

附图8示出了根据一个实施例的查询，该查询包括重复的MATCH表达式和通过查询的变换所生成的概念上有效的查询。

附图9示出了查询计划的SHOWPLAN输出的一部分，该查询计划包括如由一个实施例针对示例图查询所生成的多步骤序列。

附图10示出了根据一个示例实施例的用于处理查询以生成并且执行物理查询计划的方法的流程图，该物理查询计划包括第一多步骤序列。

附图11示出了根据一个示例实施例的用于通过生成包括第二多步骤序列的物理查询计划来处理查询并且用于确定要执行第一多步骤序列和第二多步骤序列中的哪一个的方法的流程图。

附图12示出了根据一个示例实施例的用于确定要执行第一多步骤序列和第二多步骤序列中的哪一个的方法的流程图。

附图13示出了根据一个示例实施例的用于确定要执行第一多步骤序列和第二多步骤序列中的哪一个的备选方法的流程图。

附图14示出了根据一个示例实施例的通过生成包括多步骤序列的查询计划来处理查询的方法的流程图，该多步骤序列包括被配置为将数据传送给查询计划的一个或多个其他步骤的步骤。

附图15示出了根据一个示例实施例的用于通过生成查询计划来处理查询的方法的流程图，该查询计划还包括第一子计划和第二子计划，第一子计划和第二子计划分别被配置为生成子计划结果，并且其中第二子计划在后续执行期间重新使用第一子计划的子计划结果。

附图16示出了用于通过在查询计划的执行期间重新生成查询计划的一部分来处理查询的方法的流程图。

附图17是可以被用于实施各个实施例的示例基于处理器的计算机系统的框图。

当结合附图时，根据下文所阐述的详细描述，本文中所描述的实施例的特征和优点将变得更加明显，在附图中，相似的附图标记贯穿全文标识对应的元件。在附图中，相似的附图标记通常表示相同的功能类似和/或结构类似的元件。元件首次出现的附图由对应附图标记中的(多个)最左边的数字指示。

具体实施方式

I.介绍

本说明书和附图公开了并入所公开的实施例的特征的一个或多个实施例。实施例的范围不仅限于本文中所公开的方面。所公开的实施例仅例示了预期的范围，并且还涵盖了所公开的实施例的修改版本。实施例由所附权利要求书限定。

说明书中对“一个方面”、“实施例”、“示例实施例”等的引用指示所描述的实施例可以包括特定的特征、结构或特点，但是每个实施例可能不一定包括特定的特征、结构或特点。此外，这样的短语不一定指相同的实施例。进一步地，当结合实施例描述特定的特征、结构或特点时，可以认为，结合其他实施例影响这样的特征、结构或特点在本领域的技术人员的知识范围内，无论是否明确描述。

如下描述了许多示例性实施例。应注意，本文中所提供的任何节/小节标题都不旨在是限制性的。贯穿本文档描述了实施例，并且任何类型的实施例可以被包括在任何节/小节下。此外，在任何节/小节中所公开的实施例可以以任何方式与在相同的节/小节和/或不同的节/小节中所描述的任何其他实施例组合。

II.示例实施例

现在将关于针对被存储为关系数据库中的节点表和边表的图数据执行一种图查询来总体地描述实施例。具体地，将从生成查询计划以执行图的递归最短路径遍历的方面来描述实施例。然而，应理解，实施例不限于执行图查询或递归查询，如将在下文更详细地讨论。现在参考附图1描述实施例。

附图1示出了示例图100，附图100反映工作者(节点)之间的合作者关系(边)。附图1的图100包括分别利用附图标记102-附图标记108枚举的节点N1-节点N4。图100还包括分别利用附图标记110-附图标记116枚举的边1-边4。如上文所简要描述，节点N1 102至节点N4 108表示公司的工作者。另一方面，边1 110至边4 116表示工作者之间的关系。在该示例中，边表示“一起工作”关系。也就是说，由边连接的节点是具有合作者关系的工作者(即他们彼此合作)。附图1的图100仅仅是概念上的可视化工具。体现图100的数据必须以与附图1的图100所示出的不同地被存储。

例如，附图2示出了示例关系数据库节点表200，该示例关系数据库节点表200描述了与附图1的图中所示出的节点相关联的特性。节点表200作为表被存储在关系数据库中，并且在该示例中被命名为“雇员”。节点表200包括存储与每个节点有关的信息的三列。具体地，节点表200的每行包括节点ID、雇员姓名和角色。每个节点处的雇员姓名仅反映该雇员的姓名。在附图1的图100中，每个节点(即表的行)中所包括的雇员姓名仅仅是简写。在反映实际生产数据的实际图中，可能期望看到人员的真实姓名。

节点表200中的每个节点还包括该特定雇员的角色。例如，由图100中的节点示出并且被体现在节点表200中的雇员可以是如节点N1 102或节点N3 106处所示出的架构师、如节点N2 104处所示出的接待员、或如节点N4 108处所示出的PM(即“程序管理者”)。节点表200中所包括的每个节点还包括节点ID，该节点ID唯一地标识每个节点，并且如下文所描述，还用以标识由附图3的边表300的边连接的节点。

附图3的边表300可以同样地与节点表200一起被存储在关系数据库中。在该示例中，边表300被命名为“合作”。边表300包括以供定义每个边的三列。列是：边ID、来自节点和去往节点。每行对应于图100的边。每行中的节点ID唯一地标识每个边。每行的来自节点包括由该边连接的节点中的一个节点的节点ID，并且去往节点包括由该边连接的另一节点的节点ID。注意，在该示例中，节点表反映了“去往”和“来自”关系(即有向图)。然而，应理解，实施例能够与任何类型图、有向图或其他类型的图一起起作用。

结合节点表200和边表300，并且参考附图1，可以看到这些表反映了图100的节点以及用以将这样的节点互连的边。在实施例中，在节点表200和边表300已经被创建并且被留存到关系数据库系统之后，用户可以寻求针对数据执行图查询。

例如，附图4示出了可以被提交给示例实施例并且由示例实施例处理的示例图查询400。相对于附图5如下描述附图4。附图5示出了图示根据各种约束通过附图1的图的节点的可能遍历路径的表500。在实施例中，紧接在下文对附图4和附图5的讨论用以总体地描述查询400和这样的查询可以返回的数据的类型。将在下文进一步更详细地讨论描述用于生成物理查询计划的查询400的处理的其他实施例的细节。

附图4的查询400是根据一个实施例的示例事务-SQL(Transact-SQL“T-SQL”)图查询。查询400包括一个语句，该语句包括三个子句：SELECT子句402、FROM子句403和WHERE子句404。查询400作为雇员表、合作表以及再次雇员表的隐式JOIN，其中结果由WHERE子句404过滤。注意，因为查询正在计算递归结果，所以实施例必须将FROM子句403和WHERE子句404(包括下文所讨论的递归MATCH谓词406)一起用于计算结果，而不是严格地计算笛卡尔积。

WHERE子句404包括3个条件或谓词406、408和410。谓词406指定将仅包括起始节点n1与结束节点n2之间的最短路径的递归MATCH条件，其中节点n1和节点n2分别满足谓词408和谓词410。谓词408要求每个匹配的起始节点的角色都等于‘架构师’。类似地，谓词410要求每个匹配的结束节点的角色都等于‘PM’。然后，通过将WHERE子句404的条件应用于SELECT语句402的结果来生成查询400的查询结果。具体地，查询结果将返回每个架构师与每个程序管理者之间的最短路径，如附图1的图100中所示出，并且如由节点表200和边表300所体现的。

通过考虑附图5可以更好地理解查询400的查询结果。附图5的表500示出了根据各种约束通过附图1的图100的节点的可能遍历路径。表500包括三列，包括：所有路径502、架构师与程序管理者之间的所有路径504以及所有架构师与程序管理者之间的最短路径506。在附图5的表500中所示出的路径假设没有节点可以被遍历一次以上。然而，应理解，既不需要也不假设特定的遍历约束或规则。例如，可以创建类似的遍历表，假设没有边可以被遍历一次以上，或其中循环(loop/cycle)被允许达到某个最大路径长度。

表500的第一列示出了图100中的、从每个节点通过所有路径到所有其他节点的所有可能的遍历路径。例如，参考附图1的图100，考虑列502的左上象限，其中示出了开始于图100的节点N1 102处并且结束于其他节点N2-N4中的每个节点处的5条路径。具体地，路径包括：N1到N2、N1到N2到N3、N1到N2到N3到N4、N1到N2到N4以及N1到N2到N4到N3。可以示出，这是从N1到其他节点N2-节点N4的可能遍历路径的详尽列表(并且其中在任何路径中都不准许遍历节点一次以上的循环(cycle/loop))。从N2、N3和N4到所有其他节点的路径分别在表500的列502的右上、左下和右下象限中图示。仅出于上下文和完整性起见而提供了该遍历路径详尽列表，因为例如，评估查询400所需的对图100的遍历通常不会在除架构师(即N1和N3)以外的任何节点上开始。然而，在实施例中，可以执行双向遍历，由此在从架构师和程序管理者两者(但没有其他节点)开始并且工作直到遍历在中间相遇为止的两个方向上遍历图100。

现在考虑表500的列504，其中约束被置于遍历路径上。具体地，列504图示了附图1的图100的遍历路径，其中开始节点限于架构师，而结束节点限于程序管理者。如附图2的节点表200中所示出，只有一个雇员具有对应于节点N4 108的PM的角色。因此，列504中的所有路径必须在N4上结束。类似地，图100的仅N1和N3对应于具有架构师角色的雇员，然后这要求列504的路径必须始终在节点N1或节点N3上开始。明显的，列504的路径是这样的路径的详尽列表。

最后，考虑表500的列506，其中对列504中所示出的以其他方式有效的遍历路径施加了附加约束。具体地，列506中所示出的路径不仅满足要产生列504中的路径所需的条件，而且还构成所有架构师与所有程序管理者之间的最短路径(如由跳数所测量的，因为在该情况下，边都具有相等的权重)。因此，在N1与N4之间以及在N3与N4之间只有一条路径，并且这些路径是相应端点之间的最短路径。列506中所示出的路径基于附图4的查询400所返回的行。

尽管可以注意到，如附图5的表500中所示出的路径的定序暗示了图100的深度优先遍历，但是应理解，实施例不限于任何特定的遍历算法。实际上，如本领域中所理解，被采用以执行遍历的算法可以根据图的类型(例如加权边、负边权重)和/或被解决的特定类型的最短路径问题而变化。在实施例中，最短路径算法可以包括戴克斯特拉算法、贝尔曼-福特算法、A*搜索算法、费洛伊德(Floyd-Warshall)算法、约翰逊(Johnson)算法、维特比算法以及如本领域中已知的其他算法。实施例可以实施这些算法中的一个或多个算法的递归版本以执行最短路径遍历，该最短路径遍历是执行查询100所必需的，并且可以以各种方式来进行。例如，附图6示出了根据一个示例实施例的示例多步骤序列602，该示例多步骤序列602可以被包括在用于执行图查询和其他类型的查询的物理查询计划中。基于以下关于多步骤序列602的讨论，其他结构和操作实施例对于(多个)有关领域的技术人员将是明显的。

在一个实施例中，多步骤序列602是可以被包括在查询计划中的一种逻辑和物理序列运算符。如附图6中所描绘的多步骤序列602包括初始步骤606、中间步骤608和最终步骤610。尽管多步骤序列602在附图6中被描绘为具有三个步骤，但这样的配置被图示为典型示例，并且多步骤序列的其他实施例可以包括更少的步骤或更多数目的执行步骤。此外，在要执行的特定最终步骤被保留为运行时决策的情况下，多步骤序列可以包括多于一个的最终步骤。注意，多步骤序列也可以是被重复一次或多次的单一步骤。其他实施例仅涉及存在的单一步骤。步骤606和步骤608中的每个步骤可以被配置为经由一个或多个执行路径614-624将执行控制传递给多步骤序列602的一个或多个其他步骤。最终步骤610被配置为将执行控制和查询子结果612传递回查询执行组件，诸如查询执行引擎712的多步骤查询计划执行器714，如在附图7中所描绘并且如将在下文更详细地讨论的。现在将总体地描述多步骤序列602的实施例，包括由多步骤序列602使能的各功能性方面。将按照步骤606、步骤608和步骤610来描述这样的实施例。然而，应理解，多步骤序列602的实施例不限于仅包含这些特定步骤或步骤类型的多步骤序列。现在参考附图6描述实施例。

在实施例中，附图6的多步骤序列602可以通过将多步骤序列602的实例视为普通序列运算符但具有宽松的执行约束和扩展的步骤间通信能力来理解。普通序列运算符通常驱动广泛的更新计划，并且从首个到最后以纯序列顺序执行序列的每个子代。这样的序列的每个子代通常更新不同的对象，并且仅返回由序列的最后一个子代所生成的那些行。

另一方面，多步骤序列(诸如多步骤序列602)是具有许多不同能力的更灵活的序列运算符。例如，多步骤序列602的实施例当被包括在可执行的物理查询计划中时可以根据所生成的多步骤序列的详情来使以下能力中的一个或多个能力变成可能：

·将查询计划细分为单独的步骤，这些单独的步骤可以按任意顺序被执行，并且可以被重复以准许灵活、高效的递归执行；

·在步骤之间传送任意数据，包括全部的或部分的结果集；

·一个或多个步骤的多个备选计划，其中计划之间的执行选择被推迟到执行为止(例如串行计划与并行计划，取决于在执行期间所确定的基数)；

·步骤之间的适应，包括：并行性、用以解释对存储器需求的高估或低估的适应性存储器授权、基数估计；以及

·对许多应用的适用性，包括：交错执行、参数敏感计划和/或双向执行。

在实施例中，多步骤序列602的初始步骤606、中间步骤608和最终步骤610可以分别包括单个物理或逻辑SQL查询运算符。然而，在其他一些实施例中，多步骤序列602的步骤可以包括一个或多个物理或逻辑SQL查询运算符。在一个实施例中，物理运算符可以包括任何类型的物理运算符，诸如例如散列匹配、表插入、并入连接、嵌套循环、索引插入、非聚集索引更新、并行性、排序、拆分、流聚合、表扫描以及如本领域中可能已知的其他类型的SQL物理运算符。在实施例中，逻辑查询运算符可以包括例如分支和分段重新分区、各种连接运算符、不同(distinct)和不同排序(distinct sort)、部分聚集、联合以及如本领域中已知的其他类型的SQL逻辑运算符。

当执行包括多步骤序列602的实例的查询计划时，多步骤序列602的初始步骤606是要执行的多步骤序列的第一步骤。在一个实施例中，初始步骤606被配置为执行以生成初始步骤结果，并且然后将执行控制传递给不同的步骤或其自身。然而，在一些实施例中，取决于由初始步骤606生成的步骤结果，执行控制可以通过经由执行路径616传递执行控制而传递给包括中间步骤608的任何其他步骤。同样地，初始步骤606可以经由执行路径618将执行控制传递给最终步骤610。备选地，初始步骤606可以将执行控制传递给可以被包括在多步骤序列602中并且如由附图6中所描绘的一组竖直省略号表示(执行路径未示出)的任何其他步骤(包括最终步骤610，确定执行应该终止的步骤)。出于描述多步骤序列602的实施例的目的，在本文中假设初始步骤606经由执行路径616将执行控制传递给中间步骤608。

在实施例中，附图6中的多步骤序列602的中间步骤608可以被配置为从多步骤序列602的先前执行的步骤接收执行控制。在接收到执行控制之后，包括中间步骤608的实施例可以被配置为执行以生成中间步骤结果，并且在下文中将执行控制传递给多步骤序列602中的任何其他步骤，包括中间步骤608本身。实施例可以包括通过准许多步骤序列步骤(诸如中间步骤608)执行自身而使能的若干有用特征。例如，在实施例中，递归查询(如上文所讨论的这样的递归最短路径图查询)可以以简单的方式来实施，而不需要用户自定义制作递归查询或递归CTE，并且从而还避免与那些解决方案相关联的性能问题。附加地，通过准许中间步骤608(以及类似中间步骤608的中间步骤的其他实例)将执行控制传递给多步骤序列602中的任何其他步骤，使多步骤序列602在实施例中能够以任意顺序执行步骤、能够根据在运行时确定的实际步骤结果执行备选子计划、能够根据在运行时计算出的基数估计来适应查询的存储器或性能需求、并且能够使如上文所讨论的其他特征成为可能。

在执行以生成中间步骤结果之后，中间步骤608可以将执行控制传递给多步骤序列602的任何其他步骤。中间步骤608可以仅运行一次以生成中间步骤结果，并且在其后将执行控制传递给另一步骤。同样地，即使其中中间步骤608被递归地执行(即通过重复执行其自身以对由先前迭代生成的结果进行操作)，通常最终也将达到终止条件或递归深度限制，并且中间步骤608将向某一其他步骤传递执行控制。注意，在其他一些实施例中，步骤可以重复执行而不终止(即无限循环)。出于描述多步骤序列602的实施例的目的，在本文中假设中间步骤608经由执行路径618将执行控制传递给最终步骤610。

在实施例中，附图6中的多步骤序列602的最终步骤610可以被配置为从多步骤序列602的任何先前执行的步骤(包括从中间步骤608)经由执行路径618接收执行控制。多步骤序列602的最终步骤610被配置为多步骤序列602中的最终执行步骤。在实施例中，最终步骤610被配置为生成查询子结果612，该查询子结果包括针对多步骤序列602的整个执行的结果。在实施例中，查询子结果612可以部分地基于由多步骤序列602的步骤所生成的任何先前步骤结果。在接收到执行控制并生成查询子结果612之后，使多步骤序列602的实施例能够将查询子结果612和执行控制传递给任何其他查询运算符、步骤、步骤序列或多步骤序列、或传递回查询执行引擎(例如附图7的查询执行引擎712的多步骤查询计划执行器714，如将在下文进一步详细讨论)。实施例可以生成多步骤序列602的实例并将其并入到用于执行计划100的查询计划中，并且可以以各种方式来这样做。

例如，附图7示出了根据一个示例实施例的示例关系数据库系统702的框图，该示例关系数据库系统702包括被配置为生成包括多步骤序列602的查询的多步骤查询计划生成器710。基于以下关于关系数据库系统702的讨论，其他结构和操作实施例对于(多个)有关领域的技术人员将是明显的。

关系数据库系统702包括查询预处理器706、查询优化器708、查询执行引擎712和(多个)关系数据存储库716。查询优化器708包括多步骤查询计划生成器710。查询执行引擎712包括多步骤查询计划执行器714。查询预处理器706被耦合到查询生成实体704。关系数据库系统702的这些特征描述如下。

在实施例中，如附图7中所示出的关系数据库系统702的查询预处理器706被配置为接受来自查询生成实体704的查询400。出于说明性目的，如下相对于作为附图4的查询400的接收到的查询来描述关系数据库系统702，但是在实施例中，其他查询可以由系统702接收和处理。查询生成实体704可以对于关系数据库系统702本地地提供查询400(例如，从终端或Microsoft SQL Server Management Studio)，或经由网络(诸如例如因特网)远程地提供查询400。然而，网络可以包括一个或多个网络，诸如局域网(LAN)、广域网(WAN)、企业网络，并且可以包括有线和/或无线部分中的一个或多个。可以被用于提供向关系数据库系统702的查询的计算设备的示例例如包括但不限于台式计算机、膝上型计算机、平板计算机、上网本、智能手机、可穿戴式计算设备等。

尽管关系数据库系统702被描述为单片组件，关系数据库系统702也可以被实施为包括服务器的任何数目的计算设备，并且可以包括任何类型和数目的其他资源，包括支持与如上文所描述经由网络连接的计算设备的通信和这些计算设备之间的通信的资源。在实施例中，可以以任何方式来组织实施关系数据库系统702的服务器，包括被分组为服务器机架(例如每个机架8至40个服务器，被称为节点或“刀片服务器”)、服务器集群(例如2至64个服务器，4至8个机架等)或数据中心(例如数千个服务器、数百个机架、数十个集群等)。在实施例中，包括关系数据库系统702的服务器可以被共同定位(例如，与相关联的组件(诸如备用电源、冗余数据通信、环境控制等)一起被容纳在一个或多个附近的建筑物中)以形成数据中心，或可以其他方式被布置。因此，在实施例中，关系数据库系统702可以包括数据中心的分布式集合中的数据中心。

如附图7中所示出，查询预处理器706被配置为接收由查询生成实体704提交的查询400，并在其上执行某些操作以生成适于由查询优化器708进一步处理的查询的表示。这样的操作可以包括但不限于由解析器和代数化器组件(为了简化说明而未示出)执行的解析器和代数化器操作。在一个实施例中，查询预处理器706输出查询处理器树718，该查询处理器树718是查询400的逻辑表示。在一个实施例中，查询处理器树718可以通过将查询400的原始文本翻译成具有表示表访问的叶节点和表示关系运算符(诸如关系连接)的内部节点的树结构而被获得。查询优化器708被配置为接收由查询预处理器706输出的查询处理器树718，并且处理查询处理器树718以生成用于查询的查询计划720。特别地，现在将总体地描述关系数据库系统702以及查询优化器708的多步骤查询计划生成器710的实施例。将从处理附图4的查询400方面来描述这样的实施例，生成包括附图6的多步骤序列602的实例的查询计划720用于执行查询400。然而，应理解，关系数据库系统702的实施例不严格限于如附图6中所图示的多步骤序列。现在参考附图4和附图6描述实施例。

为了方便起见，查询400在本文中在下文被再现：

SELECT*FROM Employees n1，WorkingWith e1，Employees n2

WHERE MATCH(shortest_path(n1(-(e1)-＞n2)+)and

n1.Role＝′Architect′and

n2.Role＝′PM′

生成以供执行查询400的查询计划720始于查询预处理器706，其中T-SQL查询400的文本被解析以部分地确定查询400是否包括重复的MATCH表达式。例如，查询400包括如下重复的MATCH表达式：

MATCH(shortest_path(n1(-(e1)-＞n2)+)

在实施例中，当解析器在查询中遇到重复的MATCH表达式时，对该查询进行标记以指示应当使用递归多步骤序列来生成查询计划720。

在一个实施例中，当传入查询需要递归多步骤序列时，诸如在查询400的情况下，关系数据库系统702的查询预处理器706被配置为执行将查询400初始变换为查询部分，该查询部分是生成被并入到查询计划720中的递归多步骤序列所必要的。特别地，每个重复的MATCH表达式必须被映射到锚定成员、递归成员和以类似于递归CTE的方式明确引用递归成员的外部SELECT查询。

查询预处理器706的实施例还可以被配置为在从左到右和从右到左两个方向上扩展重复的MATCH表达式，其中实施例允许查询在任一方向上执行重复的MATCH表达式，例如：

MATCH(shortest_path(n1(-(e1)-＞n2＜-(e2)-n3)+))

在实施例中，上文提及的变换和扩展可以由关系数据库系统702的查询预处理器706部分地执行以产生如被提供给查询优化器708的查询处理器树718。查询优化器708的实施例可以被配置为当查询优化器708确定查询计划720应该包括多步骤序列602的实例时，使用多步骤查询计划生成器710来生成查询计划720。例如，并且如上文所讨论，查询预处理器706的解析器功能性可以包括查询处理器树718中的标志，如被提供给查询优化器708，并且指示评估查询400所需的特定处理。在一个实施例中，查询优化器708可以其后在查询处理器树718中检测标志，并且指导多步骤查询计划生成器710创建递归多步骤序列以用于包括在查询计划720中。

如上文所讨论，查询预处理器706的实施例可以被配置为执行例如查询802的初始变换，以将查询802的重复的MATCH部分至少扩展成锚定成员、递归成员和外部选择查询。例如，考虑附图8。附图8示出了根据一个实施例的查询802，该查询802包括重复的MATCH表达式和由查询的变换生成的概念上有效的查询。为方便起见，附图8的查询802在下文被再现：

SELECT*FROM n1，n2，n3，e1，e2

WHERE MATCH(shortest_path(n1(-(e1)-＞n2-(e2)-＞n3)+))

附图8的有效查询804示出了查询802及其重复的匹配谓词(即，“match(shortest_path(n1(-(e1)-＞n2-(e2)-＞n3)+))到等效锚定成员808、递归成员810和外部选择查询812的概念性扩展。应理解，有效查询804表示非物理的概念上的变换，并且不表示从其生成查询计划720的查询。

在实施例中，附图7的关系数据库系统702可以以各种方式使用查询预处理器、查询优化器708、多步骤查询计划生成器710、查询执行引擎712和多步骤查询计划执行器714以生成包括多步骤序列的查询计划，并且这样的序列同样地可以包括各种逻辑和物理计划运算符，如上文所讨论。例如，附图9示出了查询计划的SHOWPLAN输出900的一部分，其包括多步骤序列906，如由一个实施例针对示例图查询所生成的多步骤序列906。如SHOWPLAN输出900中所示出的多步骤序列906从由关系数据库系统702的一个实施例生成的物理查询计划中被摘录，并且包括各种逻辑和物理计划运算符。现在参考附图4的查询400和附图6的多步骤序列602来描述附图9的SHOWPLAN输出900。

除了图查询902包括FOR PATH表达式以外，图查询902实质上与附图4的查询400相同。在实施例中，FOR PATH选项用于标记相关联的别名以用于稍后的验证。具体地，在查询中重复的MATCH表达式中必须使用以FOR PATH选项开头的任何别名。因此，为这些查询创建的相应查询计划将是相同的，并且对查询400的所有讨论在本文中同样地适用于附图9的图查询902以及SHOWPLAN输出900的所有其他讨论，代替参考查询400和附图4。

多步骤序列906是附图6的多步骤序列602的一个示例，如上文详细讨论。在SHOWPLAN输出900中，多步骤序列906由序列SHOWPLAN运算符904表示。如上文所讨论，多步骤序列可以被认为是一种特殊类型的序列，并且尽管序列SHOWPLAN运算符904被标记为“序列”，但是它仍然作为多步骤序列进行操作，如下文更详细地详述。

如上文所详述并且在附图6中所示出的，多步骤序列的实施例至少包括初始步骤、中间步骤和最终步骤。多步骤序列904包括五个步骤：谓词步骤908、谓词步骤910、递归设置步骤912、递归步骤914和最终步骤916。在多步骤序列904中，谓词步骤908用作第一步骤。谓词步骤910、递归设置步骤912和递归步骤914中的每个都是中间步骤。最终步骤916包括多步骤序列904的最终步骤。为方便起见，将参考附图4和查询400讨论这些步骤中的每个步骤，查询400如本文中下文所再现：

SELECT*FROM

Employee n1，

WorkingWith e1，

Employee n2

WHERE MATCH(shortest_path(n1(-(e1)-＞n2)+)and

n1.Role＝′Architect′and

n2.Role＝′PM′

附图9的谓词步骤908和谓词步骤910分别执行与谓词408和谓词410有关的查询操作。谓词步骤908找到针对图100的最短路径遍历的所有起始节点。更具体地，谓词步骤908找到雇员表中‘角色’等于‘架构师’的所有行，并将这些行存储在临时表中。类似地，谓词步骤910找到针对最短路径遍历图110的所有结束节点。更具体地，谓词步骤910找到雇员表中‘角色’等于‘PM’的所有行，并将这些行存储在临时表中。尽管谓词步骤908是多步骤序列906的第一步骤，但谓词步骤910可以与初始步骤一样容易地使用，因为这些操作彼此独立。同样，并且由于相同的原因，谓词步骤908和谓词步骤910可以同时执行。在任何事件中，无论谓词步骤908和谓词步骤910中的哪一个执行第二次，该步骤都将被视为中间步骤。

递归设置步骤912同样是中间步骤。递归设置步骤912是路径遍历的开始。递归设置步骤912找到距起始节点中的每个起始节点一跳的所有节点。更具体地，递归设置步骤912取回由谓词步骤908存储在临时表中的结果，确定哪些行距那些节点中的每个节点一跳，并将那些结果存储在临时表中。参照附图1的图100以及附图2的节点表200，可以看出，节点N1和节点N3是如由谓词步骤908所确定的起始节点，并且递归设置步骤912将该节点N2确定为距节点N1一跳的唯一节点，且将节点N2和节点N4确定为距节点N3一跳的节点。在递归设置步骤912将这些结果存储在临时表中之后，并且执行控制被传递给递归步骤914。

递归步骤914被配置为递归地遍历图100的节点，以确定每个架构师与每个PM之间的最短路径。更具体地，递归步骤914以递归设置步骤912的结果(即距起始节点一跳的节点)开始，并且确定距那些节点一跳的节点，并继续递归地执行递归步骤914以找到下一级的所有节点，直到没有更多的节点被找到为止。备选地，并且当以广度优先的方式遍历时，当路径被发现时和/或在所有可能的结果被找到的情况下，能够终止递归。在递归步骤914的每次迭代期间，找到的节点被存储在临时表中，并且在递归结束时，临时表将包含整个结果集。

最终步骤916从递归步骤914所使用的临时表中取回结果集，并使那些结果冒泡通过查询计划的其余部分(未示出)。

在实施例中，附图7的关系数据库系统702可以以各种方式用于使用多步骤序列来执行图查询或其他类型的查询。例如，附图10示出了根据关系数据库系统702的示例实施例的用于处理查询以生成并执行包括第一多步骤序列的物理查询计划的方法的流程图1000。继续参考附图7描述流程图1000。基于以下关于流程图1000和附图7的关系数据库系统702的讨论，其他结构和操作实施例对于(多个)有关领域的技术人员将是明显的。

流程图1000以步骤1002开始。在步骤1002中，在数据库应用中接收查询。例如，在附图7的关系数据库系统702中，查询预处理器706从查询生成实体704接收查询400。如上文所描述，查询400可以包括例如T-SQL查询。

在步骤1004中，处理查询以生成查询计划，该查询计划至少包括第一执行步骤集，第一执行步骤集被配置为被执行以生成第一查询子结果，并且其中第一执行步骤集包括如下一些其他步骤：

·初始步骤，被配置为被执行以在接收执行控制之后生成第一步骤结果以及将执行控制传递给与初始步骤不同的步骤；

·至少一个中间步骤，被配置为在接收执行控制之后生成第二步骤结果以及将执行控制传递给执行步骤集中的任何步骤；以及

·最终步骤，被配置为在接收执行控制之后，至少部分地基于初始步骤结果和中间步骤结果，来生成第一查询子结果。

例如，在附图7的关系数据库系统702中，查询预处理器706可以被配置为预处理查询400以生成查询处理器树718，该查询处理器树718被查询优化器708接收。结合多步骤查询计划生成器710，查询优化器708被配置为生成包括多步骤序列602的实例的查询计划720，所有这些都在上文进行了详细描述。

流程图1000在步骤1006处继续。在步骤1006处，通过将执行控制传递给查询计划的执行步骤集中的初始步骤来执行查询计划，以至少部分地基于第一查询子结果来生成最终查询结果。例如，并且如上文所讨论，关系数据库系统702的查询优化器708被配置为将查询计划720传递给查询执行引擎712。查询计划720包括多步骤序列602的实例。例如，查询计划720可以包括类似于附图9的多步骤序列906的多步骤序列。在实施例中，查询执行引擎712的多步骤查询计划执行器714可以被配置为通过将执行控制传递给查询计划中的第一步骤来执行查询计划720。查询计划中的第一步骤可以包括例如如附图6中所示出的多步骤序列602的初始步骤606。在例如多步骤序列602如同附图9的多步骤序列906一样操作的情况下，查询执行引擎712的多步骤查询计划执行器714将执行控制传递给多步骤序列906的谓词步骤908，该谓词步骤908用作上文在步骤1004处所讨论的初始步骤。

执行多步骤序列906以确定计算图查询902所需的图遍历的起始节点，如上文所详细讨论。这样的起始节点被存储在临时表中，并且包括上文关于步骤1004所讨论的第一步骤结果。在执行多步骤序列906的谓词步骤908之后，查询执行引擎712的多步骤查询计划执行器714被配置为将执行控制传递给中间步骤，如上文关于步骤1004所讨论。

例如，查询执行引擎712的多步骤查询计划执行器714可以将执行控制传递给多步骤序列906的谓词步骤910。在谓词步骤910的执行完成之后，查询执行引擎712的多步骤查询计划执行器714可以并且将执行控制传递给多步骤序列906中的下一步骤，在该情况下是递归设置步骤912。一旦完成了递归设置步骤912的执行，则可以将执行控制传递给递归步骤914。

如上文所讨论，递归步骤914被配置为以由查询400的详情所指示的方式递归地遍历基础图，并将结果存储在临时表中。多步骤序列906的最终步骤916被配置为生成如上文关于步骤1004所讨论的第一查询子结果。更具体地，最终步骤916应当取回在递归步骤914处所确定的最终结果，并返回这样的结果作为第一查询子结果。通过前述描述，第一查询子结果至少部分地基于初始步骤结果(即遍历的起始节点)和中间步骤结果(即图遍历的结果)。

在完成了多步骤序列906的执行之后，查询执行引擎912可以将执行控制传递给查询计划720中的下一步骤(如果存在)。通过该描述以及至少上文附图6和附图9的详细描述可以了解，在步骤1006处所生成的最终查询结果必须至少部分地基于由例如多步骤序列906生成的第一查询子结果。

在对流程图1000的步骤1002-步骤1006的前述讨论中，还应该理解，有时，这样的步骤可以以不同的顺序或甚至与其他步骤同时执行。例如，在实施例中，在步骤1004中处理查询以生成查询计划的执行步骤可以在并行执行这样的生成的不同部分的情况下进行。

如上所述，附图7的关系数据库系统702的关系数据库系统702可以以各种方式操作以处理查询。例如，在实施例中，查询预处理器706、查询优化器708和多步骤查询计划生成器710可以根据流程图1000进行操作，并且可选地执行附加步骤。例如，在执行如附图10中所示出的流程图1000的方法步骤时或之后，关系数据库系统702的实施例可以根据附图11-附图16中的任一附图进行操作。

附图11描绘了根据一个示例实施例的流程图1100，其图示出了用于通过生成包括第二多步骤序列的查询计划来处理查询并且确定要执行第一多步骤序列和第二多步骤序列中的哪一个的示例方法。参考附图7的关系数据库系统702描述了流程图1100，但方法不限于该实施方式。基于以下关于流程图1100的讨论，其他结构和操作实施例对于(多个)有关领域的技术人员将是明显的。

在流程图1100的步骤1102中，生成查询计划以包括第二执行步骤集，第一执行步骤集和第二执行步骤集中的每个被交替地执行以生成第一查询子结果，并且处理查询包括确定要执行哪个执行步骤集。例如，附图7的关系数据库系统702可以接收查询400，其需要具有附加的多步骤序列602的查询计划720，并且其中多步骤序列中的每个可以交替地执行。例如，可能难以在运行时之前确定给定查询应当作为串行计划还是作为并行计划执行。查询优化器708的多步骤查询计划生成器710可以被配置为检测这样的分歧，并且生成查询计划720以包括串行计划和并行计划两者。进一步地，查询计划720可以被配置为还包括可以在运行时确定要执行哪个计划的步骤。

附图12示出了用于确定应当执行紧接上文关于附图11所讨论的第一执行步骤集和第二执行步骤集中的哪一个的方法的流程图1200。流程图1200在步骤1202处开始。在步骤1202处，至少部分地基于查询计划的任何其他执行步骤的步骤结果或查询计划的任何其他执行步骤集的中间查询结果来确定要执行第一执行步骤集和第二执行步骤集中的哪一个。例如，由查询优化器708结合多步骤查询计划生成器710所生成的查询计划720可以包括附加执行步骤或附加执行步骤集(例如多步骤序列)，其结果被用于确定应该执行第一多步骤序列和第二多步骤序列中的哪一个。这样的步骤或执行步骤集可以被配置为例如更精确地估计或确定查询的某一部分的基数，并且其后选择性能更高的执行步骤集。实施例可以确定第一执行步骤集和第二执行步骤集中的哪一个应该以其他方式执行。例如，考虑附图13的流程图1300。

附图13示出了根据一个示例实施例的用于确定要执行第一执行步骤集和第二执行步骤集中的哪一个的备选方法的流程图1300。流程图1300在步骤1302处开始。在步骤1302中，至少部分地基于查询中包括的可选参数，来确定要执行第一执行步骤集和第二执行步骤集中的哪一个。例如，如可能为(多个)有关领域的技术人员所知，可以通过例如所存储的过程将参数传递给查询。在关系数据库系统702的一个实施例中，查询优化器708和多步骤查询计划生成器710可以结合地工作以至少部分地基于哪些参数可以经由所存储的过程被传递给查询来生成包括第一执行步骤集和第二执行步骤集的查询计划720，并且缓存查询计划720以供稍后使用。在所存储的过程的后续执行期间，关系数据库系统702的实施例可以使用所存储的过程的调用中包括的参数来决定应当执行第一执行步骤集和第二执行步骤集中的哪一个。

现在转向附图14，附图14示出了根据一个示例实施例的方法的流程图1400，该方法用于通过生成包括多步骤序列的物理查询计划来处理查询，该多步骤序列包括被配置为将数据传送给查询计划的一个或多个其他步骤的步骤。如上文所讨论，关系数据库系统702的实施例可以被配置为使用查询优化器708结合多步骤查询计划生成器710来生成查询计划，这些查询计划包括多步骤序列，诸如例如多步骤序列906。如上文结合附图9的讨论所讨论的，谓词步骤908的结果被存储在临时表中，并且其后由递归设置步骤912使用，该递归设置步骤912在被执行时取回被存储在该临时表中的结果。以此方式，可以将数据从多步骤序列中的一个步骤传送给多步骤序列中的另一步骤。然而，除了临时表以外，多步骤查询计划生成器710的实施例可以生成多步骤序列，其中使步骤能够将离散的标量值传递给其他步骤。

关系数据库系统702的实施例也可以根据附图15进行操作。附图15示出了用于处理查询以生成查询计划的方法的流程图1500，该查询计划包括第一子计划和第二子计划，第一子计划和第二子计划分别被配置为生成子计划结果，并且其中第二子计划在后续执行期间重新使用第一子计划的子计划结果。流程图1500在步骤1502处开始。

在步骤1502处，生成包括至少一个执行步骤的第一子计划。例如，在实施例中，查询优化器708可以结合多步骤查询计划生成器710进行操作以生成查询计划720以包括执行步骤或执行步骤集(即多步骤序列)。流程图1500的操作在步骤1504处继续。

在步骤1504处，执行第一子计划以生成第一子计划结果。例如，并且如上文结合至少附图6、附图7和附图9的讨论所讨论的，多步骤序列602的实例可以由查询执行引擎712的多步骤查询计划执行器714执行以生成查询子结果。

在步骤1506处，至少部分地基于第一子计划结果来生成包括至少一个执行步骤的第二子计划，第二子计划被配置为当由查询执行引擎执行时生成第二子计划结果，并且其中第二子计划的任何后续执行将重新使用第一子计划结果。在一个实施例中，关系数据库系统702的查询优化器708和多步骤查询生成器710可以被配置为生成至少部分地取决于查询子结果的多步骤序列602。这样的多步骤序列可以包括步骤1506的第二子计划。当然，第二子计划(可能是多步骤序列)的执行本身将生成第二子计划结果。查询优化器708的实施例可以被配置为缓存第二子计划以供重新使用以用于该计划的后续执行，并且无需重新运行第一子计划来获得第一子计划结果。

备选地，实施例可以根据附图16的流程图1600起作用，图示出了用于通过在查询计划的执行期间重新生成查询计划的一部分来处理查询的方法。流程图1600在步骤1602处开始。在步骤1602处，在查询计划的执行期间重新生成查询计划的一部分。例如，关系数据库系统702的实施例结合查询优化器708和多步骤查询计划生成器710可以生成包括第一多步骤序列和第二多步骤序列602的查询计划720。在查询计划720的执行期间，实施例可以使例如对应于第二多步骤序列的查询计划720的部分被重新编译。在查询优化器708在优化查询以产生查询计划720期间做出不正确的假设的情况下，这样的运行时重新编译可能是有利的，并且这样的不正确的假设或通过执行第一多步骤序列被发现。

注意，例如，提供了对关系数据库系统702的操作的前述一般描述，并且关系数据库系统702的实施例可以以不同于上文所描述的方式的方式进行操作。此外，并非附图10-附图16的流程图1000-流程图1600的所有步骤在所有实施例中都需要被执行。此外，流程图1000和流程图1500的步骤可以以与一些实施例中所示出的顺序不同的顺序被执行。

III.示例计算机系统实施方式

关系数据库系统702、流程图1000、流程图1100、流程图1200、流程图1300、和/或流程图1400、流程图1500、和/或流程图1600可以以硬件、或与软件和/或固件结合的硬件来实施。例如，关系数据库系统702、流程图800、流程图900、流程图1000、流程图1100、流程图1200、流程图1300、和/或流程图1400可以被实施为计算机程序代码/指令，这些计算机程序代码/指令被配置为在一个或多个处理器中被执行并被存储在计算机可读存储介质中。备选地，关系数据库系统702、流程图1000、流程图1100、流程图1200、流程图1300、流程图1400、流程图1500、和/或流程图1600可以被实施为硬件逻辑/电气电路装置。

例如，在一个实施例中，关系数据库系统702、流程图1000、流程图1100、流程图1200、流程图1300、流程图1400、流程图1500和/或流程图1600中的一个或多个、以任何组合可以一起被实施在SoC中。SoC可以包括集成电路芯片，该集成电路芯片包括处理器(例如中央处理单元(CPU)、微控制器、微处理器、数字信号处理器(DSP)等)、存储器、一个或多个通信接口、和/或其他电路中的一个或多个，并且可以可选地执行接收到的程序代码和/或包括嵌入式固件以执行功能。

附图17描绘了实施例可以被实施的计算设备1700的示例性实施方式。例如，可以使用类似于固定或移动计算机实施例中的计算设备1700的一个或多个计算设备(包括计算设备1700的一个或多个特征和/或备选特征)来实施关系数据库系统702。本文中所提供的对计算设备1700的描述是出于说明的目的而提供的，并且不旨在是限制性的。如(多个)有关领域的技术人员所知，实施例可以在其他类型的计算机系统中被实施。

如附图17中所示出，计算设备1700包括被称为处理器电路1702的一个或多个处理器、系统存储器1704以及将包括系统存储器1704的各种系统组件耦合到处理器电路1702的总线1706。处理器电路1702是在一个或多个物理硬件电路设备元件和/或集成电路设备(半导体材料芯片或裸片)被实施为中央处理单元(CPU)、微控制器、微处理器和/或其他物理硬件处理器电路的电气和/或光学电路。处理器电路1702可以执行在计算机可读介质中所存储的程序代码，诸如操作系统1730的程序代码、应用程序1732、其他程序1734等。总线1706表示几种类型的总线结构中的任何一种或多种，包括使用各种总线架构中的任何一种的存储器总线或存储器控制器、外围总线、加速图形端口以及处理器或本地总线。系统存储器1704包括只读存储器(ROM)1708和随机存取存储器(RAM)1710。基本输入/输出系统1712(BIOS)被存储在ROM 1708中。

计算设备1700还具有以下驱动中的一个或多个：用于从硬盘读取和写入硬盘的硬盘驱动1714、用于从可移除磁盘1718读取或写入可移除磁盘1718的磁盘驱动1716和用于从可移除光盘1722读取或写入可移除光盘1722的光盘驱动1720(诸如CD ROM、DVD ROM或其他光学介质)。硬盘驱动1714、磁盘驱动1716和光盘驱动1720分别通过硬盘驱动接口1724、磁盘驱动接口1726和光盘驱动接口1728连接到总线1706。驱动及其相关联的计算机可读介质为计算机提供了计算机可读指令、数据结构、程序模块和其他数据的非易失性存储。尽管描述了硬盘、可移除磁盘和可移除光盘，但是可以使用其他类型的基于硬件的计算机可读存储介质来存储数据，诸如闪速存储器卡、数字视频磁盘、RAM、ROM和其他硬件存储介质。

多个程序模块可以被存储在硬盘、磁盘、光盘、ROM或RAM上。这些程序包括操作系统1730、一个或多个应用程序1732、其他程序1734和程序数据1736。应用程序1732或其他程序1734可以包括例如用于实施关系数据库系统702、流程图800、流程图900、流程图1000、流程图1100、流程图1200、流程图1300和/或流程图1400的计算机程序逻辑(例如计算机程序代码或指令)和/或本文中所描述的其他实施例。

用户可以通过输入设备(诸如键盘1738和指点设备1740)将命令和信息录入计算设备1700中。其他输入设备(未示出)可以包括麦克风、操纵杆、游戏板、卫星天线、扫描仪、触摸屏和/或触摸板、用以接收语音输入的语音识别系统、用以接收手势输入的手势识别系统等。这些和其他输入设备通常通过耦合到总线1706的串行端口接口1742被连接到处理器电路1702，但是可以通过其他接口(诸如并行端口、游戏端口或通用串行总线(USB))被连接。

显示屏1744还经由接口(诸如视频适配器1746)被连接到总线1706。显示屏1744可以在计算设备1700外部或被并入计算设备1700中。显示屏1744可以显示信息以及作为用于接收用户命令和/或其他信息(例如通过触摸、手指手势、虚拟键盘等)的用户界面。除了显示屏1744以外，计算设备1700可以包括其他外围输出设备(未示出)，诸如扬声器和打印机。

计算设备1700通过适配器或网络接口1750、调制解调器1752或用于通过网络建立通信的其他装置连接到网络1748(例如因特网)。调制解调器1752(其可以是内部的或外部的)可以经由串行端口接口1742连接到总线1706，如附图17中所示出，或可以使用包括并行接口的另一接口类型连接到总线1706。

如本文中所使用，术语“计算机程序介质”、“计算机可读介质”和“计算机可读存储介质”被用于指物理硬件介质(诸如与硬盘驱动1714相关联的硬盘、可移除磁盘1718、可移除光盘1722)、其他物理硬件介质(诸如例如RAM、ROM、闪速存储器卡、数字视频磁盘、压缩磁盘、MEM、基于纳米技术的存储设备)以及其他类型的物理/有形硬件存储介质。这样的计算机可读存储介质与通信介质区分开并且不重叠(不包括通信介质)。通信介质在调制数据信号(诸如载波)中实施计算机可读指令、数据结构、程序模块或其他数据。术语“调制数据信号”意味着以对信号中的信息进行编码的方式来设置或改变的其一种或多种特点的信号。通过示例而非限制，通信介质包括无线介质(诸如声学无线介质、RF无线介质、红外无线介质和其他无线介质)以及有线介质。实施例还涉及与涉及计算机可读存储介质的实施例分离并且不重叠的这样的通信介质。

如上所述，计算机程序和模块(包括应用程序1732和其他程序1734)可以被存储在硬盘、磁盘、光盘、ROM、RAM或其他硬件存储介质上。这样的计算机程序也可以经由网络接口1750、串行端口接口1742或任何其他接口类型来接收。当由应用执行或加载时，这样的计算机程序使得计算设备1700能够实施本文中所描述的实施例的特征。因此，这样的计算机程序表示计算设备1700的控制器。

实施例还涉及包括在任何计算机可读介质上所存储的计算机代码或指令的计算机程序产品。这样的计算机程序产品包括硬盘驱动、光盘驱动、存储设备包、便携式存储器棒、存储器卡以及其他类型的物理存储硬件。

VI.附加示例实施例

在一个实施例中，提供了一种系统。系统包括：查询预处理器，被配置为接收查询并且构造逻辑运算符查询树；查询优化器，被配置为至少部分地基于逻辑运算符查询树来生成可执行查询计划，该可执行查询计划至少包括被配置为被执行以生成第一查询子结果的执行步骤集，该执行步骤集包括：初始步骤，被配置为被执行以在接收执行控制之后生成第一步骤结果，以及将执行控制传递给与初始步骤不同的步骤；至少一个中间步骤，被配置为在接收执行控制之后生成第二步骤结果，以及将执行控制传递给执行步骤集中的任何步骤；以及最终步骤，被配置为在接收执行控制之后，至少部分地基于初始步骤结果和中间步骤结果，来生成第一查询子结果；以及查询执行引擎，被配置为通过将执行控制传递给可执行查询计划的执行步骤集中的初始步骤来执行查询，以至少部分地基于第一查询子结果来生成最终查询结果。

在前述系统的实施例中，可执行查询计划还包括：第二执行步骤集，被配置为生成第二查询子结果；并且查询执行被配置为执行查询以进一步至少部分地基于第二查询子结果来生成最终查询结果。

在前述系统的另一实施例中，至少一个中间步骤还被配置为将执行控制传递给可执行查询计划中的任何执行步骤。

在前述系统的一个实施例中，查询优化器被配置为生成可执行查询计划，以包括如下执行步骤，该执行步骤被配置为将数据传送给可执行查询计划中的一个或多个其他执行步骤。

在前述系统的另一实施例中，查询优化器还被配置为通过包括第三执行步骤集和第四执行步骤集来生成可执行查询计划，第三执行步骤集和第四执行步骤集中的每个被配置为被交替地执行；并且查询执行引擎还被配置为确定在可执行查询计划正在被执行时要执行第三执行步骤集和第四执行步骤集中的哪一个。

在前述系统的一个实施例中，查询执行引擎被配置为至少部分地基于以下至少一项来确定要执行第三执行步骤集和第四执行步骤集中的哪一个：可执行查询计划的任何执行步骤的步骤结果、或可执行查询计划的任何其他执行步骤集的中间查询结果。

在前述系统的另一实施例中，查询执行引擎被配置为至少部分地基于可选参数是否被包括在查询中来确定要执行第三执行步骤集和第四执行步骤集中的哪一个。

在前述系统的一个实施例中，其中，为了生成可执行查询计划，查询优化器还被配置为：生成第一子计划，第一子计划包括至少一个执行步骤，该至少一个执行步骤被配置为生成第一子计划结果；执行第一子计划，以生成第一子计划结果；以及至少部分地基于第一子计划结果来生成包括至少一个执行步骤的第二子计划，该第二子计划被配置为当由查询执行引擎执行时生成第二子计划结果，并且其中第二子计划的任何后续执行将重新使用第一子计划结果。

在前述系统的另一实施例中，查询优化器被配置为在可执行查询计划的执行期间重新生成可执行查询计划的至少一部分。

提供一种执行查询以生成查询结果的计算机实现的方法。在一个实施例中，计算机实现的方法包括：在数据库应用中接收查询；处理查询，其中所述处理查询包括：生成针对查询的查询计划，查询计划至少包括如下执行步骤集，该执行步骤集被配置为被执行以生成第一查询子结果，该执行步骤集包括：初始步骤，被配置为被执行以在接收执行控制之后生成第一步骤结果，以及将执行控制传递给与初始步骤不同的步骤；至少一个中间步骤，被配置为在接收执行控制之后生成第二步骤结果，以及将执行控制传递给该执行步骤集中的任何步骤；以及最终步骤，被配置为在接收执行控制之后，至少部分地基于初始步骤结果和中间步骤结果，来生成第一查询子结果；以及通过将执行控制传递给查询计划的该执行步骤集中的初始步骤来执行查询。以至少部分地基于第一查询子结果来生成最终查询结果。

在前述方法的一个实施例中，查询计划还包括：第二执行步骤集，被配置为生成第二查询子结果；并且其中所述执行查询以生成最终查询结果还包括：执行查询以进一步至少部分地基于第二查询子结果来生成最终查询结果。

在前述方法的一个实施例中，至少一个中间步骤包括递归步骤，该递归步骤被配置为生成递归步骤结果并且除非递归步骤结果满足预定义条件，否则将执行控制传递给自身。

在前述方法的另一实施例中，生成针对查询的查询计划包括：生成查询计划以包括如下执行步骤，该执行步骤被配置为将数据传送给查询计划中的一个或多个其他执行步骤。

在前述方法的一个实施例中，所述生成针对查询的查询计划包括：生成查询计划以包括第三执行步骤集和第四执行步骤集，第三执行步骤集和第四执行步骤集中的每个被配置为被交替地执行；并且其中所述处理该查询还包括：确定要执行第三执行步骤集和第四执行步骤集中的哪一个。

在前述方法的另一实施例中，所述确定要执行第三执行步骤集和第四执行步骤集中的哪一个包括：至少部分地基于以下至少一项来确定要执行第三执行步骤集和第四执行步骤集中的哪一个：查询计划的任何其他执行步骤的步骤结果、或查询计划的任何其他执行步骤集的中间查询结果。

在前述方法的一个实施例中，所述确定要执行第三执行步骤集和第四执行步骤集中的哪一个包括：至少部分地基于查询中包括的可选参数，来确定要执行第三执行步骤集和第四执行步骤集中的哪一个。

在前述方法的另一实施例中，生成针对查询的查询计划还包括：生成第一子计划，该第一子计划包括至少一个执行步骤，该至少一个执行步骤被配置为生成第一子计划结果；执行第一子计划，以生成第一子计划结果；以及至少部分地基于第一子计划结果来生成包括至少一个执行步骤的第二子计划，该第二子计划被配置为当由查询执行引擎执行时生成第二子计划结果，并且其中第二子计划的任何后续执行将重新使用第一子计划结果。

在前述方法的实施例中，所述处理查询还包括：在查询计划的执行期间重新生成查询计划的至少一部分。

在又一实施例中，提供了一种计算机可读存储设备，其上记录有计算机程序代码，该计算机程序代码当由计算设备的至少一个处理器执行时使至少一个处理器执行操作。

在前述计算机可读存储设备的一个实施例中，操作包括：在数据库应用中接收查询；处理查询，其中所述处理查询包括：生成针对查询的查询计划，该查询计划至少包括如下执行步骤集，该执行步骤集被配置为被执行以生成第一查询子结果，该执行步骤集包括：初始步骤，被配置为被执行以在接收执行控制之后生成第一步骤结果，以及将执行控制传递给与初始步骤不同的步骤；至少一个中间步骤，被配置为在接收执行控制之后生成第二步骤结果，以及将执行控制传递给该执行步骤集中的任何步骤；以及最终步骤，被配置为在接收执行控制之后，至少部分地基于初始步骤结果和中间步骤结果，来生成第一查询子结果；以及执行查询以通过将执行控制传递给查询计划的执行步骤集中的初始步骤来至少部分地基于第一查询子结果来生成最终查询结果。

在前述计算机可读存储器设备的另一实施例中，至少一个中间步骤包括递归步骤，该递归步骤被配置为生成递归步骤结果并且除非递归步骤结果满足预定义条件，否则将执行控制传递给自身。

V.结论

虽然上文已经对本申请的各种实施例进行了描述，但应理解，这些实施例仅通过示例而非限制被呈现。(多个)有关领域的技术人员将理解，在不脱离如所附权利要求书中所定义的本申请的精神和范围的情况下，可以在其中进行形式和细节上的各种改变。因此，本申请的宽度和范围不应受上文所描述的示例性实施例中的任何一例限制，而是应该只根据以下权利要求书和其等效物来定义。