用于在多个节点协调计算的方法和装置

摘要

本发明描述了一种允许从数据库管理系统内部并行注册和调用外部函数的程序化接口，用于在多个节点协调计算。在一个实施例中，每个节点响应于从数据库系统接收的命令，执行用于使程序启动执行计算的过程。响应于在数据库系统接收到查询，将多个命令发送给在每个相应过程同时执行计算的过程。从每个过程接收结果，并基于所接收的结果来完成语句的执行。

权利要求

1.一种用于在多个节点协调计算的方法，包括：

在所述多个节点中的每个节点处，响应于从数据库系统接收的命令，执行用于启动程序以执行所述计算的相应过程，其中，在所述多个节点中的每个所述节点处，每个程序执行任何数据库系统的外部例程；以及在所述数据库系统处，接收符合由所述数据库系统内的数据库服务程序支持的数据库语言的语句，其中，所述语句指定用于执行所述计算的所述程序，其中，所述语句不指示所述多个节点中的哪些节点将参与执行所述计算；以及，响应于接收所述语句：将用于执行所述计算的多个命令同时发送到每个所述相应过程；

接收来自每个所述相应过程的结果；以及

基于从每个所述相应过程接收的所述结果，完成所述语句的处理；

其中，接收用于执行所述计算的每个相应过程执行如下步骤：以非阻塞方式启动所述程序；以及

响应于所述程序的结束，获取通过所述程序产生的结果，并将所述结果发送给所述数据库系统。

2.一种用于在多个节点协调计算的方法，包括：

在数据库系统处，接收符合由所述数据库系统内的数据库服务程序支持的数据库语言的语句，其中，所述语句指定用于执行所述计算的程序，其中，所述语句不指示所述多个节点中的哪些节点将参与执行所述计算；以及响应于接收所述语句：

将用于执行所述计算的多个命令发送到多个相应过程，所述过程用于响应于所述多个命令，启动多个相应程序以执行所述计算，其中，在与每个所述相应程序相同的节点处，每个过程执行任何数据库系统的外部例程；接收来自每个所述相应过程的结果；以及基于从每个所述相应过程接收的所述结果，完成所述语句的处理；

其中，接收用于执行所述计算的每个相应过程执行如下步骤：以非阻塞方式启动所述程序；以及

响应于所述程序的结束，获取通过所述程序产生的结果，并将所述结果发送给所述数据库系统。

3.根据权利要求2所述的方法，还包括：

从所述多个能够执行所述计算的节点中确定节点的群组，

其中，所述多个相应过程对应于所述节点的所述群组。

4.根据权利要求3所述的方法，其中，所述多个节点包括至少一个不包括在所述节点的所述群组中的节点。

5.根据权利要求3所述的方法，其中，所述确定是基于由所述多个节点中的每个节点支持的并行度。

6.根据权利要求3所述的方法，其中，将在所述多个节点中的每个节点上执行的每个相应过程配置成响应于从所述数据库系统接收的命令启动程序以执行所述计算，而且还包括访问指定在程序与数据容器之间的关联的注册表，其中，所述确定是基于在所述程序与所述数据容器之间的所述关联。

7.根据权利要求3所述的方法，还包括访问指定数据容器的相应属性的注册表，其中，所述确定是基于将所述数据容器的所述相应属性与所述语句中的参数进行匹配。

8.根据权利要求3所述的方法，还包括访问指定与程序和数据容器相关联的分块函数的注册表，其中，所述确定是基于执行与所述程序和所述数据容器相关联的分块函数的结果。

9.根据权利要求1所述的方法，其中，通过所述数据库系统执行所述同时发送、接收结果、以及完成处理的步骤。

10.根据权利要求1所述的方法，其中，使用与所述数据库系统不同类型的硬件、操作系统软件、或应用软件，实现所述多个节点中的至少一个。

11.根据权利要求1所述的方法，其中，在所述多个节点中的每个节点上执行的所述相应过程用于响应于从所述数据库系统接收的命令，启动程序以执行所述计算。

12.根据权利要求1所述的方法，其中，每个所述相应过程指示程序在数据容器上执行所述计算。

13.根据权利要求2所述的方法，其中，通过所述数据库系统执行所述发送所述多个命令、接收结果、以及完成处理的步骤。

14.根据权利要求2所述的方法，其中，在多个节点中的一个节点上执行所述多个相应过程中的每个过程，以及其中，使用与所述数据库系统不同类型的硬件、操作系统软件、或应用软件，实现所述多个节点中的至少一个节点。

15.根据权利要求2所述的方法，其中，所述相应过程中的每个过程用于响应于所述指令，启动所述程序以执行所述计算。

16.根据权利要求2所述的方法，其中，每个所述相应过程指示所述程序在数据容器上执行所述计算。

17.根据权利要求15所述的方法，其中，由每个所述相应过程启动的所述程序中的至少一些并行执行。

18.一种用于在多个节点协调计算的装置，包括：

执行模块，用于在所述多个节点中的每个节点处，响应于从数据库系统接收的命令，执行用于启动程序以执行所述计算的相应过程，其中，在所述多个节点中的每个所述节点处，每个程序执行任何数据库系统的外部例程；以及接收和处理模块，用于在所述数据库系统处，接收符合由所述数据库系统内的数据库服务程序支持的数据库语言的语句，其中，所述语句指定用于执行所述计算的所述程序，其中，所述语句不指示所述多个节点中的哪些节点将参与执行所述计算；以及，响应于接收所述语句：将用于执行所述计算的多个命令同时发送到每个所述相应过程；

接收来自每个所述相应过程的结果；以及

基于从每个所述相应过程接收的所述结果，完成所述语句的处理；

其中，接收用于执行所述计算的每个相应过程执行如下步骤：以非阻塞方式启动所述程序；以及

响应于所述程序的结束，获取通过所述程序产生的结果，并将所述结果发送给所述数据库系统。

19.一种用于在多个节点协调计算的装置，包括：

接收模块，用于在数据库系统处，接收符合由所述数据库系统内的数据库服务程序支持的数据库语言的语句，其中，所述语句指定用于执行所述计算的程序，其中，所述语句不指示所述多个节点中的哪些节点将参与执行所述计算；以及处理模块，用于响应于接收所述语句：

将用于执行所述计算的多个命令发送到多个相应过程，所述过程用于响应于所述多个命令，启动多个相应程序以执行所述计算，其中，在与每个所述相应程序相同的节点处，每个过程执行任何数据库系统的外部例程；

接收来自每个所述相应过程的结果；以及

基于从每个所述相应过程接收的所述结果，完成所述语句的处理；

其中，接收用于执行所述计算的每个相应过程执行如下步骤：以非阻塞方式启动所述程序；以及

响应于所述程序的结束，获取通过所述程序产生的结果，并将所述结果发送给所述数据库系统。

20.根据权利要求19所述的装置，还包括：

群组确定模块，用于从所述多个能够执行所述计算的节点中确定节点的群组，其中，所述多个相应过程对应于所述节点的所述群组。

21.根据权利要求20所述的装置，其中，所述多个节点包括至少一个不包括在所述节点的所述群组中的节点。

22.根据权利要求20所述的装置，其中，所述确定是基于由所述多个节点中的每个节点支持的并行度。

23.根据权利要求20所述的装置，其中，所述装置将在所述多个节点中的每个节点上执行的每个相应过程配置成响应于从所述数据库系统接收的命令启动程序以执行所述计算，而且还访问指定在程序与数据容器之间的关联的注册表，其中，所述确定是基于在所述程序与所述数据容器之间的所述关联。

24.根据权利要求20所述的装置，其中，所述装置还访问指定数据容器的相应属性的注册表，其中，所述确定是基于将所述数据容器的所述相应属性与所述语句中的参数进行匹配。

25.根据权利要求20所述的装置，其中，所述装置还访问指定与程序和数据容器相关联的分块函数的注册表，其中，所述确定是基于执行与所述程序和所述数据容器相关联的分块函数的结果。

26.根据权利要求18所述的装置，其中，通过所述数据库系统执行所述同时发送、接收结果、以及完成处理的步骤。

27.根据权利要求18所述的装置，其中，使用与所述数据库系统不同类型的硬件、操作系统软件、或应用软件，实现所述多个节点中的至少一个。

28.根据权利要求18所述的装置，其中，在所述多个节点中的每个节点上执行的所述相应过程用于响应于从所述数据库系统接收的命令，启动程序以执行所述计算。

29.根据权利要求18所述的装置，其中，每个所述相应过程指示程序在数据容器上执行所述计算。

30.根据权利要求19所述的装置，其中，通过所述数据库系统执行所述发送所述多个命令、接收结果、以及完成处理的步骤。

31.根据权利要求19所述的装置，其中，在多个节点中的一个节点上执行所述多个相应过程中的每个过程，以及其中，使用与所述数据库系统不同类型的硬件、操作系统软件、或应用软件，实现所述多个节点中的至少一个节点。

32.根据权利要求19所述的装置，其中，所述相应过程中的每个过程用于响应于所述指令，启动所述程序以执行所述计算。

33.根据权利要求19所述的装置，其中，每个所述相应过程指示所述程序在数据容器上执行所述计算。

34.根据权利要求32所述的装置，其中，由每个所述相应过程启动的所述程序中的至少一些并行执行。

说明书

用于在多个节点协调计算的方法和装置

技术领域

[0001] 本发明涉及数据库系统，更具体地，涉及异构型计算机系统间的复杂计算。

背景技术

[0002] 科学计算中的一种常见情况是在多个异构型(heterogeneous，多机种)环境间运行复杂计算，存取和处理以各种不同格式存储的数据。例如，一种复杂计算是在各种遗传序列及其引用的数据库内搜索遗传物质的DNA匹配。异构型环境包括不同的且通常不兼容的硬件、操作系统、以及应用软件的组合。通常，单独购买这些不同的系统以用作特殊的需要，并且企业可能使信息在多个计算机系统间传播。由于系统厂商试图提供超过其竞争者的产品的竞争优势，不同的系统根据定义几乎不兼容。由于SQL实现、数据库定义、以及通信机制的不同，甚至基于结构化查询语言(SQL)标准的关系数据库管理系统(DBMS)和关系模型可能是不兼容的。因此，很难完成联合用于执行复杂计算的异构型系统的任务。

[0003] 在多个异构型环境间执行复杂计算中，数据库管理系统通常被用作计算结果的最终储存库，以及用作计算中使用的一些数据的来源。然而，将另一异构型系统(即，数据库管理系统)并入到环境中给已经很难的执行复杂计算的任务带来了额外的复杂度。

[0004] 例如，一种用于管理这种复杂计算的方法被称为多级处理，其中，复杂计算被分解成多个步骤，每个步骤由用户提交并在同构型平台上整体地和独立地发生。将每个计算的结果结合在单独步骤中并且加载到结果数据库中。计算步骤的协调由人工完成或使用某种形式的工作流引擎，并且全部的计算结果仅在批处理模式下执行之后可得到，而且不可交互。由此，在多级处理方法中，与数据库系统的集成很差并且是非交互式的，基本上将数据库系统缩减成对于先前执行的数据运行的结果的事后用户接口。此外，执行计算的协调难以以稳固且可升级(scalable)的方式实现。

[0005] 更加交互的方法是将特定的协调步骤在可由用户提交的数据库查询中编码。当用户将特定编码查询提交到数据库系统时，执行该查询，使得数据库系统启动复杂计算的各种子分量(sub-component)并将结果结合在一起。以这种方法将查询编码需要开发者对每种异构型系统有很深的认识，将基于此执行计算的部分，并且在数据库外部管理部分的执行。这种方法在范围内不常用，而只用于特定计算。

[0006] 另一种方法是支持并行查询、分组、以及一些数据库系统的两阶段提交机制，该数据库系统允许在多个(同构型)数据库实例间执行单个查询。在这种方法中，将在不兼容系统上出现的数据移入到一个或多个数据库中并且将用于执行计算的算法重写到数据库内的函数。然而，这种转移-重写方法很昂贵且耗费时间，而且需要硬件投资以使每个节点都能够执行数据库实例、数据库管理系统软件、以及数据库管理和应用开发资源。此外，重写将在数据库中执行的算法可能不可行。

[0007] 因此，需要一种稳固、可升级、可交互、以及便宜的方法来在多个异构型数据库系统间执行复杂计算。

发明内容

[0008] 本发明着眼于这些以及其他需要，提供了一种程序化(programmatic)接口，允许从数据库管理系统内部并行注册和调用外部函数。因此，本发明的一个方面涉及一种用于在多个节点协调计算的方法，每个节点响应于从数据库系统接收的命令，执行用于启动程序来执行计算的过程。响应于在数据库系统接收到查询，将多个命令发送到用于对每个所述相应过程同时执行计算的过程。从每个过程接收结果，并基于所接收的结果来完成语句的执行。

[0009] 本发明的另一方面涉及一种用于根据在多个节点设置的多个数据容器来协调计算的方法和软件。响应于在指定用于执行计算的外部例程的数据库系统接收到语句或查询，将用于执行计算的命令发送到用于启动程序来执行计算的过程。从每个过程接收结果，并基于所接收的结果来完成语句的执行。在一个实施例中，基于不同的标准(例如，并行度和可用线程的数量)，确定用于执行计算的节点的群。

[0010] 仅通过说明多个特定实施例和实例(包括用于实现本发明的最佳方式)，本发明的其他方面、特征、以及优势将从下面的详细描述中更加显而易见。本发明还可以是其他不同的实施例，其若干细节可在多种明显的方面进行修改，而所有的修改均不背离本发明的主旨和范围。因此，认为附图和说明实质上是说明性的，而不是限制性的。

附图说明

[0011] 通过附图中的实例来描述本发明，但是不局限于此，在附图中相同的参考标号表示类似的元件，其中：

[0012] 图1示出了可用于采用本发明实施例的异构型环境。

[0013] 图2是示出本发明一个实施例的操作的流程图。

[0014] 图3示出了可用于实现本发明实施例的计算机系统。

具体实施方式

[0015] 描述了一种用于复杂计算的系统、方法、以及软件。在以下的描述中，为了解释的目的，描述了多个特殊的细节，以提供对本发明的透彻理解。然而，很显然，对本领域技术人员来说，在没有这些特定细节或等同配置的情况下，也可以实现本发明。在其他的实例中，以框图形式示出已知的结构和设备，以避免不必要地使本发明不清楚。

[0016] 在数据库管理系统中，数据存储在一个或多个数据容器中，每个容器包含记录，并且将每个记录内的数据组织成一个或多个字段。在关系数据库系统中，数据容器指的是表格，记录指的是行，而字段指的是列。在面向对象数据库中，数据容器指的是对象类别，记录指的是对象，而字段指的是属性。其他数据库结构可使用其他术语。

[0017] 实现本发明的系统并不局限于任何特定类型的数据容器或数据库结构。然而，为了解释，这里所用的术语和实例将典型地与关系数据库有关。由此，这里所用的术语“表格”、“行”、以及“列”分别指的是数据容器、记录、以及字段。

[0018] 系统描述

[0019] 图1是异构型环境100的示意图，其中，可采用本发明实施例来执行复杂计算。具体地，异构型环境100包括数据库管理系统(DBMS)平台101以及异构型平台103。如果硬件、操作系统、以及应用软件的组合与DBMS平台101上的硬件、操作系统、以及应用软件不同或不兼容，则平台103可认为是异构型的。根据使用环境，本发明的实施例可包括一个或多个附加异构型平台105。即使在此将平台103和105描述为异构型的，平台103和105中的一个或多个可能与DBMS平台101为同构型，并且仍获得一些来自本发明其他方面的优势。因此，本发明在同构型或混合同构型/异构型环境中是有优势的。

[0020] DBMS平台101提供了一种用户接口或用于通过多个异构型平台103和105执行复杂计算的应用程序，协调异构型平台103和105之间的复杂计算，以及用作来自异构型平台103和105的复杂计算结果的存储库。在一个实施例中，DBMS平台101包括用于从用户或指定复杂计算的应用程序中接收查询的数据库服务程序107、用于存储复杂计算结果以及参与复杂计算的其他数据的关系数据库109、用于协调分布式复杂计算的编程接口注册表
111、以及基于编程接口注册表111中的信息由编程接口生成的占位(stub)程序113。下面，将更加详细地描述编程接口注册表111和占位程序113。

[0021] 占位程序113用于打开到在异构型平台103上执行的监督程序(daemon，守护程序)115以及在异构型平台105上执行的相应监督程序(未示出)的网络连接或其他通信链接。在不丧失一般性的情况下，为了便于描述，相对于异构型平台103单独描述异构型平台103和105的系统结构。优选地，监督程序115是持续空闲的后台处理，直到被来自占位程序113的通信激活。当被激活时，监督程序115用于启动、传递自变量给、以及停止执行一个或多个计算程序117。一个或多个计算程序117可以与用于执行复杂计算的外数据库119相互作用，并将结果最终返回到用于在关系数据库109中的存储和对用户或应用程序的呈现的数据库服务程序107。

[0022] 优选地，占位程序113和监督程序115用于启动在一个或多个异构型平台103和105上的一个或多个计算程序117，以同时实现并行度。在这种结构中，数据库服务程序107通过占位程序113命令监督程序115启动具有合适自变量的一个或多个计算程序117，或将自变量传递给已经在运行的计算程序117，或终止已经在运行的计算程序117。监督程序
115以非阻塞方式依次启动每个被请求的计算程序117，在启动所有被请求的计算程序117之后，等待计算程序117结束。随着每个计算程序117结束，将结果返回给DBMS平台101中的请求过程。在一个实施例中，监督程序115以非阻塞方式将自变量传递给正在运行的计算程序117，即，不等待来自计算程序117的结果。数据库服务程序107可将停止执行一个或多个正在运行的计算程序117的请求作为较早请求的一部分发送。在检验来自相同源的两个请求之后，监督程序115可以终止请求的计算程序117。

[0023] 此外，用监督程序115注册的每个计算程序117可具有默认的并行度(例如，执行的并发线程的数量)。这个默认值可由来自数据库服务程序107的请求覆盖，以启动具有不同线程数量的计算程序117。在本实施例中，每个监督程序115维持可用线程的池并且追踪每个线程的状态(忙、空闲)，通过将计算程序117附加到线程并将该线程标记成忙来启动计算程序117。如果在池中的所有线程都为忙，则创建新的线程，直到达到可配置的线程。监督程序115将使更新的数据库服务程序107保持在其线程池的状态(例如，线程的总量以及忙线程的数量)，使得数据库服务程序107能够管理与其他异构型平台105的并行启用。

[0024] 因此，提供了一种在DBMS平台101内的程序化接口，其允许数据库查询以对在每个目标异构型平台103和105上管理多个且优选并行的计算程序117的监督程序115产生运行时间调用。这些监督程序115代表数据库服务程序107管理非数据库程序117的执行。产生占位程序113的编程接口和执行计算程序117的监督程序115可以做成是通用的，所以应用程序开发者不需要知道分布式计算机系统101的结构，就可以编写用于执行复杂计算的数据库查询。此外，协调复杂计算的编程接口注册表111的安装可以为由数据库管理员执行的一次操作。结果，获得用于在异构型计算机系统间执行复杂计算的稳固、可升级、以及易于使用的系统。

[0025] 编程接口注册表

[0026] 在一个实施例中，在DBMS平台101内运行的应用程序可以使用访问编程接口注册表111的非阻塞编程接口调用在其他平台103和105上的并行程序117，编程接口注册表包含表示异构型平台103和105以及存在于异构型平台103和105上的计算程序117的性能的信息，足以协调异构型平台103和105之间的复杂计算。该信息优选地由数据库管理员输入，但是该信息的一部分可以在查询中交互地获得。例如，编程接口注册表111中的信息可用于识别对于DBMS平台101可用的异构型平台103和105，并且将计算程序117与用于数据库服务程序107中的程序化接口的这些平台103和105相关联，使得数据库服务程序可以通知可在监督程序对应的平台103和105上运行的程序117的每个监督程序115。

[0027] 在编程接口注册表111中的注册数据可表示：计算程序117的名称、每个在异构型环境100中可运行单个计算程序117的计算机103、用于调用计算程序117的程序自变量(号码、数据类型、位置)，该计算机103上的该计算程序117可以对其运行的数据集、以及运行计算程序117的结果如何返回(通常为，记录的集合)。编程注册表111中的其他更多管理类型的信息可包括：计算程序117是每次都需要重新启动还是可继续运行并且为每次调用接受新的自变量的指示；是否允许部分结果(如果运行该计算程序117请求的计算机103和105的适当子集未能返回有效结果，则结果可被认为是部分的)；以及计算程序117的默认值及最大并行度。

[0028] 编程接口注册表111还包括关于异构型环境101内每个计算机103的数据。该信息可包括：每个计算机103和105的名称、用于创建在DBMS平台101与异构型平台103之间的通信链接的连通性数据(IP地址、鉴别信息)；对于来自异构型平台103的确认的超时间隔；在从超时接口接收确认失败之后的重试次数；心跳间隔(在计算机103上的监督程序115的状态信息之间的时间量)；以及错过的心跳量，如果遇到，则表示计算机对异构型平台103的失败。此外，使用编程接口注册表111中的线程池状态和最大允许容量信息能够进一步协调并行调用。

[0029] 一旦注册，例如通过用于设置编程接口注册表111的编程接口程序，为每个由编程接口注册表111注册的计算程序117产生程序上的占位程序113。以数据库服务程序103内支持的编程语言编码的占位程序113提供了对计算程序117的调用接口。占位程序113的参数可包括计算程序117的自变量、将对其进行操作的数据范围、期望的并行度、以及返回类型(数据行的集合)。

[0030] 因此，任何可执行作为SQL查询的函数并返回一组结果的程序能够在可被认为是计算集群的异构型环境100中并行执行。如果将结果定义为一组行，则函数可用在SQL查询的FROM子句中，作为返回一组行的表函数。另一方面，如果函数不返回一组行(例如，整数的集合)，则该函数仍可用在SELECT列表中或对象类型的用户定义方法中。

[0031] 表函数是产生行集合或者是能够像物理数据库表一样查询或分配给PL/SQL集合变量的向量/阵列。语法上，表函数可用于诸如查询的FROM子句中数据库表的名称或诸如查询的SELECT列表中的列名称。表函数可将行集合作为输入。表函数的执行可并行，而且不需要中间阶段，返回的行可直接流向下一过程。在一个实例中，来自由表函数返回的集合的行可被流水线输送(pipeline)，或者，换句话说，在处理表函数的输入完成之后，在产生行时迭代地返回，而不是全部突然成批地返回。因此，可通过启动表函数的多线程的并行执行、消除过程之间的中间阶段、以及改进查询的响应时间，来改进表函数的流动、流水线、以及并行执行的性能。通过非流水线输送的表函数，在查询可返回单个结果行之前，构成由表函数返回的整个集合并将其返回到服务程序。当产生行时，流水线输送可使行迭代地返回。这样还减小了表函数所需的内存，这是由于对象高速缓冲存储器不需要使整个集合具体化。在产生行时，通过迭代地提供来自由表函数返回的集合的结果行，而不是等到整个集合在表或内存中分级随后返回整个集合。

[0032] 在一个实施例中，为了简化，在异构型环境101中执行的函数是叶级(leaf-level)函数，并且通过数据库服务程序107完成集合(MAX、MIN、DISTINCT等)。根据将由数据库服务程序107完成的集合(如果有的话)，可将从计算程序117流水线输送的行立即返回到用户行源，或为数据库服务程序107中的集合(aggregation)缓冲。

[0033] 操作概述

[0034] 图2示出了本发明的一个实施例的用于在多个异构型系统间协调复杂计算的操作。在步骤201中，数据库服务程序107接收包括调用编程接口注册表中列出的外部例程的查询或数据库语句，并且产生线程来处理语句中的调用。结构化查询语言(SQL)的示例性查询可表示如下：

[0035] SELECT citation_name

[0036] FROM citations c，TABLE(dna_match(“ACGTAT”))st

[0037] WHERE st.sequence_id＝c.seq_id；

[0038] 该语句是通过对两个源执行连接操作来请求一组引用名称(即，列“citation_name”)的查询，这两个源为：从在异构型环境中的计算机系统间执行外部函数“dna_match”的结果而形成的表“st”以及引用表“c”。“dna_match”外部函数是可在各种计算机系统103上执行的程序117，其访问基因组数据库119中基因序列的数据库，并且返回用于基因组数据库119中所有DNA序列的序列标识符(“sequence_id”)，该序列标识符与编辑距离(edit-distance)内自变量的核苷酸序列匹配。核苷酸是用于DNA的腺嘌呤(A)、鸟嘌呤(G)、胸腺嘧啶(T)、和胞嘧啶(C)以及用于RNA的腺嘌呤(A)、鸟嘌呤(G)、尿嘧啶(U)、和胞嘧啶(C)。在本实例中，异构型环境100包括异构型计算机系统103和105，这些异构型计算机系统具有基因序列的各种所有权数据库，每个均不得不与不同的数据库和接口竞争。引用表“c”将对于大多数用户难以理解的序列标识符(“sequence_id”＝“seq_id”)与用户容易理解的匹配序列的源引用联系起来。如上所述，期望的并行度能够在查询中留下空白符，而在这种情况下，并行度可默认为在编程接口注册表111中已经设置的程度。

[0039] 在步骤203中，分析调用，以验证在号码、类型、以及位置方面的外部例程的自变量是否正确。通过访问存储在编程接口注册表111中的函数签名，可完成该确认，其指定传到外部例程的自变量的数量以及每个位置的每个参数的类型。例如，在一种表示法中，存储在编程接口注册表111中的“dna_match”函数的函数签名可为：

[0040] FUNCTION dna_match(String pattern)RETURN SEQUENCE_D_SET；

[0041] 在该签名中，“dna_match”是外部函数，其准确地获得“String”类型的一个自变量(被称为“pattern”)。“dna_match”被指定返回以一列的表表示的一组序列标识符。如果自变量不正确(例如，两个自变量传给“dna_match”或一个号码传给“dna_match”)，则启用不被确认，并将错误返回给调用应用程序。

[0042] 一旦通过确认，执行进入步骤205，其中，确定计算机101、103、和105(被称为“节点”)“群组(cohort)”和线程，用于最终执行外部调用，以执行调用中指定的复杂计算。在不背离本发明的情况下，存在确定该群组的多种方法。在一个实施例中，将群组确定成计算机的最小量，其服从(a)请求的并行度(或在参数中指定成占位函数113或由注册表默认)，(b)在节点处的外数据库119是否能够服务于请求，(c)在每个节点的线程池中的线程的可用性，具有较大数量的可用线程的可用性优于具有较小数量的可用线程的可用性，以及(d)哪个节点被较早包括，以便改变位置。

[0043] 在步骤207中，执行占位程序113的线程请求对群组成员执行程序117，其中，群组中的每个计算机优选地支持尽可能多的并行线程，给定已经执行的工作量(例如，达到可用线程)。这些请求被产生给群组中的每个计算机上的监督程序115。如果在占位中涉及的程序117不需要对每个请求都重新启动，则请求只需要传递一组新的自变量。

[0044] 在发送请求之后，线程等待由每个目标监督程序115接收的请求的确认。如果请求超时，如由编程接口注册表111中的超时间隔所限定的，则以在编程接口注册表111中指定的次数重试该请求。如果在重试之后没有成功且不允许部分结果(也由编程接口注册表111中的值来管理)，则中止执行调用并将控制返回给应用程序。在中止调用的情况下，将中止程序请求发送给成功执行的那些群组计算机的监督程序115。

[0045] 如果所有的监督程序115成功接收请求，或者如果有足够的监督程序来产生部分结果，则在步骤209中，线程等待，以将来自所有接收请求的节点的结果集合。如果节点的心跳失败(如在编程接口注册表111中所指定的)，则线程停止等待来自那个节点的结果。如果允许部分结果并且仍可得到(即，尚有仍可返回有效结果的计算机)，则线程继续等待。否则，中止剩余请求并且控制返回到应用程序。

[0046] 最后，在步骤211中，当已经等待的线程的所有请求已经返回结果时，将结果处理成占位中指定的格式并返回到应用程序。在一个实例中，将结果一次一行地流水线输送给应用程序。

[0047] 节点与容器之间的一对一映射

[0048] 关于图2所示的方法是有效且灵活的，而且可处理各种不同的调用策略。例如，最简单的情况之一是在用于每个在关系数据库109外部的函数的节点与数据之间存在一对一映射的环境。换句话说，用编程接口注册表111将每个节点103和105注册为能够执行被编码成在文件系统内的特定位置(例如，当线程初始化时通过配置文件)访问数据或数据容器的特定体的函数。在这种情况下，占位函数113将命令发送给被注册为执行具有在SQL查询中提供的自变量的函数的所有节点中的监督程序115。具体地，将对计算集群并行执行的函数是搜索给定模式并按行返回在预定编辑距离内包含该模式的一组序列号的函数：

[0049] FUNCTION dna_match(String pattern)RETURN SEQUENCE_ID_SET；

[0050] 为了确定包含模式“ACGTAT”的序列的所有引用，在本实例中，用户对数据库服务程序107发出下列查询，如下所示：

[0051] SELECT citation_name

[0052] FROM citations c，TABLE(dna_match(“ACGTAT”))st

[0053] WHERE st.sequence_id＝c.seq_id；

[0054] 响应中，数据库服务程序107调用占位程序113，其将用“ACGTAT”作为参数的远程过程调用(RPC)发布给已为编程接口注册表111中的“dna_match”函数注册的所有节点。计算程序117的“dna_match”函数的各个实例对将序列定位在它们的文件系统119内并返回将与引用表结合的序列标识符负责。

[0055] 节点与数据容器之间的非双射映射

[0056] 上述情况的特点为节点与数据容器之间的一对一或双射映射；然而，实施例可能支持在“m”个节点和“n”个数据容器之间的非双射映射或“m-n”映射。如果一些节点共享对至少一些相同数据容器的访问，例如，通过NFS(网络文件共享)，则可能是非双射映射。在这种情况下，将附加的隐参数传给每个执行计算程序117的线程，以指示数据容器线程需要处理。数据库服务程序107不需要能够解释数据容器的结构，数据库服务程序107需要知道如何指定数据容器(例如，通过文件系统119中的路径名)以及如何映射每个函数的节点和容器。如表1所示，可将这种映射表存储在编程注册表111、关系数据库109、或其他地方中。

[0057] 表1

[0058] 函数名称 节点名称 数据容器

[0059] dna_match Dlsun l X：/disk01/sequence.dat

[0060] dna_match Dlsun l X：/disk02/sequence.dat

[0061] dna_match Dlsun2 X：/disk01/sequence.dat

[0062] dna match Dlsun3 X：/disk02/sequence.dat

[0063] protein_match Dlsun1 Y：/disk01/sequence.dat

[0064] protein_match Dlsunl Y：/disk02/sequence.dat

[0065] protein_match Dlsun2 Y：/disk01/sequence.dat

[0066] protein_match Dlsun2 Y：/disk02/sequence.dat

[0067] 表1中的每行映射将外部函数(例如，“dna_match”或“protein_match)与可执行外部函数的节点(例如，Dlsun1、Dlsun2、或Dlsun3)以及节点可处理的数据容器相关联。因此，节点Dlsun1可处理两个不同容器的“dna_match”的启用以及另外两个不同容器“protein_match”的启用，而Dlsun1只处理用于一个数据容器的一个函数(X：/disk02/sequence.dat上的“dna_match”)。当调用外部函数(例如，“Dna_match”)时，确定需要处理的数据容器组(例如，X：/disk01/sequence.dat，X：/disk02/sequence.dat)，并且基于诸如节点上的负载、期望的并行度、超高速缓冲存储器位置(期望在相同节点上执行相同函数若干次，使得线程可重新使用可能已经高速缓存的任何数据)等的标准，为群组选择分配给数据容器的节点。

[0068] 基于属性的删改(pruning)

[0069] 这里，当执行函数时，数据库服务程序107没有“删改”数据容器，即，没有减少真正需要被搜索以满足请求的数据容器的数量。应答查询可能不需要访问一些容器，所以期望避免昂贵的搜索或对数据容器的其他操作。在本实例中，可通过外部函数自身的实现者(implementer)完成删改。例如，外部函数的自变量可用于迅速确定(即，O(1)时间)特定的数据容器通过查看文件标题将不返回行。例如，如果只在E.coli的序列上期望dna_match，那么可在查询中指定E.coli自变量，如下所示：

[0070] SELECT citation_name

[0071] FROM citations c，TABLE(dna_match(“ACGTAT，“E.coli”))st[0072] WHERE st.sequence_id＝c.seq_id；

[0073] 假设在表1中给出设置，节点Dlsun1上的“dna_match”函数可以作为dna_match(Context，“X：/disk01/sequence.dat”，“ACGTAT”，“E.coli”)调用；并且如果数据容器的“X：/disk01/sequence.dat”文件的标题表示没有序列用于E.coli，则“dna_match”函数迅速返回。然而，数据库服务程序107优选地过滤出数据容器，即使在将用于调用节点上的函数的命令发送到监督程序115之前。一个解决方案是将每个数据容器与一些用户定义的属性相关联，数据库服务程序107可以使用该属性根据SQL查询过滤出容器。例如，如表2所示，用于容器映射的该函数可使用称为“sequence_type”的附加属性。

[0074] 表2

[0075] 数据容器 属性名称 属性类型 值

[0076] X：/disk01/sequence.dat sequence_type String E.coli

[0077] X：/disk02/sequence.dat sequence_type String Mouse

[0078] X：/disk01/sequence.dat sequence_date Date 02/20/97

[0079] X：/disk02/sequence.dat sequence_date Date 02/06/95

[0080] 在本实例中，可通过下列查询的WHERE子句中的附加谓词删改容器。

[0081] SELECT citation_name

[0082] FROM citations c，TABLE(dna_match(“ACGTAT”))st

[0083] WHERE st.sequence_id＝c.seq_id and st.sequence_type＝“E.coli”and st.sequence_date＞01/01/1996；

[0084] 通过这种过滤机制，根据属性类型可以支持所有的SQL操作符。

[0085] 参数过滤

[0086] 可能属性等级过滤机制不够灵活。在这些情况下，可以将用户定义的分块(partitioning，分区，分配)函数与每个函数相关联。在调用监督程序115之前调用该函数，以确定需要被访问以应答查询的数据容器组。分块函数在数据库服务程序107自身的范围内执行并且不需要并行化。除了返回一组容器之外，分块函数的签名与将要执行的函数相同，例如，

[0087] PARTITION_FUNCTION dna_match__partition(String pattern，

[0088] String[]attribute_names IN，

[0089] String[]attribute_values IN，

[0090] String[]containers OUT)；

[0091] 第一列参数与函数自身的参数相同(在这种特定的实例中，只存在一个参数，“pattern”)，根据在WHERE子句中指定的值，通过数据库服务程序107使属性名称和值通过。用户提供的“dna_match_partition”函数使用属性名称和属性值以容纳于容器中作为OUT参数，随后由占位程序113使用，以确定群组并调用各个监督程序115。

[0092] WHERE子句条件

[0093] 除了那些将数据容器删改成并行函数所需要的之外，还期望传递WHERE子句条件。例如，用户可能希望在SQL WHERE条件中提供“edit distance”。该WHERE子句不用于删改容器，而是被传到并行函数，以在过滤结果组时或在自身执行期间使用。因此，为了限制对记录在另一表中的edit_distance的搜索，可使用下列查询：

[0094] SELECT citation_name

[0095] FROM citations c，TABLE(dna_match(“ACGTAT”))st

[0096] WHERE st.sequence_id＝c.seq_id and st.sequence_type＝“E.coli ”and st.sequence_date＞01/01/1996 andSt.edit_distance＜(SELECT max(edit_distance)fromresults)；

[0097] 如上述参数删改情况所述，“sequence_type”和“sequence_date”是数据容器删改条件，并且未传给并行外部函数。另一方面，“edit_distance”条件作为隐WHRER子句上下文传给外部函数。优选地，这些WHERE子句条件被限制成标量数据类型；另外，如果WHERE子句涉及与另一行源的结合，则数据库服务程序107可能需要将WHERE子句标准流水线输送到外部函数，明显地使并行外部函数的实现复杂化。此外，如果外部函数只返回一组行作为FROM子句中的表函数，则WHERE子句上下文被传给并行外部函数。

[0098] 物理节点中的多线程

[0099] 上述的分块法可容易地展开，以适应物理节点中的多线程。如果物理节点可以针对给定函数执行达到N线程，则当在线程之间对工作分块时，可认为该节点是N逻辑节点或虚拟处理器。由于不存在群组内(intra-cohort)通信(即，在执行函数的叶级线程之间的通信)或不存在数据库控制之外的群组内通信，所以数据库服务程序107不需要尝试在相同的物理节点上集合线程。基于上述的其他参数(例如，数据容器的访问、物理节点上的负载等)选取线程和节点。

[0100] 硬件描述

[0101] 图3说明了根据本发明的实施例能够实现的计算机系统300。计算机系统300包括用于传递信息的总线301或其他通信装置，以及连接到总线301用于处理信息的处理器303。计算机系统300还包括连接到总线301用于存储由处理器303执行的信息和指令的主存储器305，例如，随机存取存储器(RAM)或其他动态存储装置。在处理器303执行指令期间，主存储器305还可用于储存临时变量或其他中间信息。计算机系统300还包括连接到总线301用于存储静态信息和处理器303的指令的只读存储器(ROM)307或其他静态存储装置。存储设备309(例如，磁盘或光盘)连接到总线301，用于持续存储信息和指令。

[0102] 计算机系统300可以经由总线301连接到诸如阴极射线管(CRT)、液晶显示器、主动矩阵显示器、或等离子显示器的用于向计算机用户显示信息的显示器311。输入装置313(例如，包括字母数字键和其他键的键盘)连接到总线301，用于将信息和指令选择传递到处理器303。另一种类型的用户输入装置是光标控制器315，例如鼠标、跟踪球、或光标方向键，用于将方向信息和命令选择传递到处理器303并用于控制显示器311上的光标移动。

[0103] 根据本发明的一个实施例，响应于执行包括在主存储器305中的指令的序列的处理器303，通过计算机系统300提供了通过多个节点协调复杂计算。这样的指令可以从诸如存储装置309的其他计算机可读介质读入主存储器305。包括在主存储器305中的指令序列的执行引起处理器303执行此处所述的处理步骤。也可以使用在多个处理序列中的一个或多个处理器来执行包括在主存储器305中的指令。在可选实施例中，可以使用硬连线电路(hard-Wiredcircuitry)来取代软件指令或者与软件指令结合来实现本发明的实施例。在另一实例中，可使用诸如现场可编程门阵列(FPGA)的可重新配置的硬件，其中，通常通过编程存储器查询表，在运行时间其逻辑门的功能和拓扑连接(connection topology)是可定制的。因此，本发明的实施例将不限于硬件电路和软件的任何特定组合。

[0104] 计算机系统300还包括连接到总线301的通信接口317。通信接口317提供连接到与局域网321连接的网络链接319的双向数据通信。例如，通信接口317可以是数字用户线路(DSL)或调制解调器、综合业务数字网(ISDN)卡、线缆调制解调器、电话调制解调器、或任何其他通信接口，用于将数据通信连接提供到相应类型的通信线路。又如，通信接口317可以是局域网(LAN)卡(例如，用于EthernetTM或异步发送模式(ATM)网络)，用于将数据通信连接提供到兼容局域网(LAN)。也可以使用无线链接。在任何这样的实例中，通信接口317发送和接收承载表示各种信息类型的数字数据流的电信号、电磁信号、或光学信号。此外，通信接口317可包括外部接口装置，例如通用串行总线(USB)接口、PCMCIA(个人计算机存储器卡国际联合会)接口等。尽管图3仅示出了单个通信接口317，也可采用多个通信接口。

[0105] 网络链接319通常可通过一个或多个网络向其他数据装置提供数据通信。例如，网络链接319可通过局域网321连接到主机323，其具有与网络325的连接(例如，广域网(WAN)或现在通常被称为“因特网”的全球分组数据通信网络)或者具有与互联网服务提供商操作的数据设备的连接。局域网321和网络325都使用电信号、电磁信号、或光学信号来传输信息和指令。与计算机系统300传输数字数据的通过各种网络的信号以及在网络链接319上并通过通信接口317的信号，是发送信息和指令的载波的示例性形式。

[0106] 计算机系统300可通过网络、网络链接319、和通信接口317发送消息和接收数据(包括程序代码)。在互联网的实例中，服务器(未示出)可通过网络325、局域网321、和通信接口317传送属于用于实现本发明的实施例的应用程序的请求代码。所接收的代码可以在其被接收时由处理器303执行，和/或储存在存储装置309或其他非易失性介质中，用于随后执行。以这种方式，计算机系统300可以以载波形式获得应用代码。

[0107] 这里使用的术语“计算机可读介质”是指参与向处理器303提供指令用于执行的任何介质。这种介质可以采取多种形式，包括但不限于非易失性介质、易失性介质、和传送介质。非易失性介质举例来说包括光盘或磁盘，例如，存储装置309。易失性介质包括动态存储器，例如，主存储器305。传送介质包括同轴电缆、铜线、和光纤，包括组成总线301的导线。传送介质还可采取声波、光波、或电磁波形式，例如，那些在射频(RF)和红外线(IR)数据通信过程中产生的声波、光波、或电磁波。计算机可读介质的一般形式包括：例如，软盘、软碟、硬盘、磁带、或者任何其他磁性介质、CD-ROM、CDRW、DVD、任何其他光介质、穿孔卡、纸带、光学标记片、任何带孔图样或其他光学公认标记的物理介质、RAM、PROM、EPROM、FLASH-EPROM、其他任何存储芯片或者盒式磁带、载波、或者任何其他计算机可读的介质。

[0108] 各种形式的计算机可读介质可参与将指令提供给处理器以执行。例如，用于实现本发明至少一部分的指令开始可承载在远程计算机的磁盘上。在这种情况下，远程计算机将指令加载到主存储器中，并使用调制解调器通过电话线发送指令。本地计算机系统的调制解调器接收电话线上的数据，并使用红外发射器将数据转换成红外信号，以及将红外信号发送到诸如个人数字助理(PDA)或便携式电脑的便携式计算装置。便携式计算装置的红外探测器接收红外信号携带的信息和指令，并将数据放到总线上。总线将数据传送到主存储器，处理器从主存储器取回并执行这些指令。在由处理器执行这些指令之前或之后，由主存储器接收的指令可随意地储存在存储装置上。

[0109] 虽然结合多个实施例和实例描述了本发明，但是本发明并不限于此，而是涵盖多种明显的修改和等同替换，其均在权利要求的范围内。