执行具有多个集合操作符的查询

摘要

依据示例，一种用于执行具有多个集合操作符的查询的方法包括在输入查询的每个输入结果表中添加附加列，该附加列使结果表的标识符与包含在输入结果表中的数据相关联。所述方法还包括对包含在输入结果表中的数据执行Union All操作以产生中间结果集合；对包含在中间结果集合中的数据执行Group By操作以产生分组结果集合，其中，Group By操作对各组行操作并对各组中的每一个返回一行；在包含每个元组存在于每个输入结果表的次数的计数的分组结果集合中添加聚合列；以及在分组结果集合上应用谓词以执行查询。

说明书

背景技术

关系数据库管理系统（RDBMS）在表中存储数据，其中，所述表是全部具有相同列的行的集合。表中的每列保持特定类型的数据用于组成行的数据。结构化查询语言（SQL）经常被用于查询、访问和操作包含在表中的数据。所述SQL语言包括集合操作符Union、 Union All、Intersect、Intersect All、 Except和Except All。复杂的SQL查询使用集合操作符Union，Intersect和Except的各种组合。

附图说明

通过示例的方式图示出本公开的特征并且不局限于下面的（一个或多个）图，其中，相同的附图标记指示相同的元件，其中：

图1示出了依据本公开的示例的计算环境的功能框图，其中，可实现本文中所公开的数据库管理器；

图2是依据本公开的示例的图1所示的机器的功能框图；

图3示出了依据本公开的示例的用于执行查询的方法的流程图；

图4A-4D分别描绘出依据本公开的示例的在图3所描绘的方法期间执行的各种操作的说明示例的图；

图5描绘出依据本公开的示例的用于生成谓词的方法的流程图；

图6示出了依据本公开的示例的可在其上实现图5所描绘的方法的集合操作符分析树的图；以及

图7图示出依据本公开的示例的计算设备的示意性表示，该计算设备可用于执行图1和2所描绘的机器的各种功能。

具体实施方式

出于简单和说明的目的，本公开主要参照其示例进行描述。在下列描述中，阐述了许多具体的细节以提供对本公开的透彻理解。然而，将显而易见的是，本公开可在不限于这些具体细节的情况下被实践。在其他实例中，一些方法和结构并未予以详细描述以免不必要地模糊本公开。

如遍及本公开所使用的，术语“包括”意指包括但不限于，术语“包含”意指包含但不限于。术语“基于”意指至少部分地基于。此外，术语“一个”旨在表示特定元件中的至少一个。

本文所公开的是用于执行具有多个集合操作符的查询的示例方法，其中，所述查询可包括集合操作符的混合。本文还公开的是用于实现示例方法的示例设备，以及在其上存储实现该示例方法的机器可读指令的示例非暂时性计算机可读介质。依据示例，用于执行查询的方法在Vertica^TM列存储数据库中被调用或实现。

本文所公开的用于执行查询的示例方法包括一组高效地消除针对集合操作符的重复的操作，而不需要在确定查询的输出时执行多个Group By操作。换言之，通过本文所公开的方法的实现，查询的结果可通过经由单一Group By操作创建至多一个哈希表来确定，而不管查询中包括的集合操作符的数量或类型。举例来说，Group By操作对各组行操作并且对各组中的每一个返回一行，例如，以从结果表中消除重复行。集合操作符包括Union、Intersect和Except。

然而，本文所公开的示例方法在不需要对该方法显著改变的情况下也可被扩展为实现Intersect All和Except All。特别是，仅可改变该示例方法以包括每个元组被示出在输出中的次数的改变。通过特定的示例，在查询select * from TableA Intersect All select * from TableB时，谓词将与Intersect查询相同，即，count(A)>0 AND（与） count(B)>0。然而，满足以上条件的每个元组必须被输出min（count(a), count(B)）次。所有剩下的操作将保持相同。在其中集合操作符为Except All的示例中，谓词将与Except的谓词相同，但是满足以上条件的每个元组必须被输出max(count(a)-count(B),0)次。

相比之下，用于执行包含一组集合操作符的查询的传统技术是执行Join操作，其每次仅接受两个输入。在这种传统技术中，对于n个不同的集合操作符，需要建立n-1个哈希表，当哈希表被建立在其中的存储器对于在给定时间要被存储的任何n-1个哈希表来说太小时，这或许是不可能的。如此，如果由于不足的存储器、哈希表必须被写入磁盘多次以保存任何哈希表，那么该查询可能执行不良。此外，这种传统技术取决于使用成本模型来选择内部和外部表。从而，如果成本模型错误地选择内部和外部表，那么所产生的Join操作可导致相对大的哈希表，这导致存储器资源的相对大的消耗。由这种传统技术所产生的相对大的哈希表还可以导致差的性能，例如，在Except操作符的情况下，因为如果Except，那么结果哈希表只可从右输入进行创建，如果右输入的大小与左输入相比非常大，那么该查询可能执行不良。这种传统技术的另一个可能的缺点是：为了消除重复输入，除在Join操作期间建立的哈希表之外，还需要建立另一个哈希表用于Group By操作。

另一种传统技术包括由Postgres实现的技术。在这种传统技术下，每个操作仅允许两个输入，并且因此涉及N个集合操作符的查询可能需要建立N-1个哈希表以确定输出。这种技术受集合操作符查询的优先级所约束。对于涉及多个集合操作符的查询，这种传统技术应用多个Group By操作，这可能是昂贵的。此外，这种传统技术在Intersect的情况下依赖于用于选择内部和外部表的成本模型，并且在Except的情况下总是选择左表。

因此，与传统的查询处理技术相比，本公开的各方面使查询的结果能够以相对高效的方式被确定，而不依赖于相对大的存储器。

首先参照图1，示出了依据示例的计算环境100的功能框图，其中，可实现在本文中所公开的数据库管理器。应该显而易见的是，图1所描绘的图表示一般化图示而且在不脱离本公开的范围的情况下，可增加其他组件或可去除、修改或重新排列现有的组件。

计算环境100被描绘为包括机器110、数据存储器120、网络130和多个客户端设备140a-140n，其中，“n”表示大于或等于1的整数。机器110（其可包括计算机、服务器等）也被描绘为包括数据库管理器112、包含表116的数据库114和包含查询集合124的存储器122。数据库管理器112用以管理数据库114，例如，访问和修改包含在数据库114的表116中的数据，对包含在表116中的数据执行查询等。例如，数据库管理器112用以执行涉及Union、Intersect、Except、Union All、Intersect All和Except All集合操作符的SQL操作。还如图1所示，数据库管理器112包括Union All执行模块216和Group By执行模块218，它们可在执行SQL操作时执行各种功能，如下面详细论述的。此外，查询集合124（其可包括查询操作的例如中间结果集合、分组结果集合等）可存储在存储器122中，存储器122可包括随机存取存储器，诸如动态随机存取存储器（DRAM）。在这点上，查询集合124可存储在存储器122中而不是存储在磁盘（诸如数据存储器120）上。因此，从一方面来看，查询集合124可能不被写入磁盘多次，而是可在存储器122中存储并进行访问。对其中可实现数据库管理器112的各种方式在下面进行更详细地描述。

表116的实际数据可被存储在数据存储器120中，数据存储器120包括易失性和/或非易失性存储器，诸如，硬盘上的光学或磁性介质、DRAM、EEPROM、MRAM、相变RAM（PCRAM）、忆阻器、闪存等。附加表，例如由集合操作符（诸如，Union、Intersect、Except等）所产生的那些也可被存储在数据存储器120中。依据示例，数据库114包括Vertica^TM列存储数据库。此外，虽然数据存储器120已被描绘为与机器110分离，但在不脱离本文所包含的公开的范围的情况下，数据存储器120可与机器110进行集成。

依据示例，机器110用以从客户端设备140a-140n中接收对包含在数据存储器120中的信息的查询，并且用以将查询操作的结果通过网络130传送到客户端设备140a-140n。客户端设备140a-140n包括台式计算机、膝上型计算机、平板计算机、个人数字助理、智能手机、蜂窝电话等中的一个或多个。此外，网络130包括IP网络，诸如，因特网、蜂窝网络、局域网、广域网等。附加或可替代地，查询可通过机器110直接输入。

现在回到图2，示出了依据示例的图1所示的机器110的功能框图。应当理解的是，机器110可以包括附加组件而且在不脱离本文所公开的机器110的范围的情况下，在本文中所描述的一些组件可被去除和/或修改。

该机器110被描绘为包括所有与图1所描绘的机器110中的那些一样的组件。图2中的机器110和数据库管理器112也被描绘为包括附加组件。特别是，机器110还被描绘为包括处理器202和通信模块204。处理器202包括微处理器、微控制器、专用集成电路（ASIC）等，并且用以在机器110中执行各种处理功能。例如，处理器202用以执行数据库管理器112和通信模块204，并且访问数据库114。处理器202还用以在存储器122中存储和访问查询集合124。通信模块114包括硬件设备、机器可读指令或其组合以使机器110能够通过网络130接收和发送数据。

数据库管理器112被描绘为包括输入/输出模块210、数据扫描模块212、列添加模块214、Union All操作执行模块216、Group By操作执行模块218、聚合模块220和谓词应用模块222。处理器202用以在执行各种操作时调用或执行模块210-222，如本文下面更详细地论述的。

依据示例，数据库管理器112包括例如存储在易失性或非易失性存储器（诸如，DRAM、EEPROM、MRAM、闪存、软盘、CD-ROM、DVD-ROM或其他光学或磁性介质等）中的机器可读指令。在这个示例中，模块210-222包括存储在存储器中的机器可读指令的模块，它们是由处理器202可执行的。依据另一个示例，数据库管理器112包括硬件设备，诸如布置在板子上的一个或多个电路。在这个示例中，模块210-222组成电路组件或单个电路，它们由处理器202控制。依据另外的示例，数据库管理器112包括具有机器可读指令的模块和硬件模块的组合。

数据库管理器112的模块210-222以其可操作的各种方式关于图3和5所分别描绘的方法300和500进行论述。应该显而易见的是，方法300和500表示一般化图示，并且在不脱离方法300和500的范围的情况下，可增加其他元件或可去除、修改或重新排列现有的元件。

首先参照图3，示出了依据示例的用于执行查询的方法300的流程图。在方法300中执行的操作仅出于说明的目的关于图4A-4D所提供的示例进行描述，并且图4A-4D所提供的示例因此在任何方面不应被解释为本公开的限制特征。

依据示例，在实现方法300之前，可例如由输入/输出模块210来接收输入查询。例如，输入/输出模块210接收由客户端设备140a通过网络130传送的输入查询。可将该输入查询转换成识别要被应用到多个表116的集合操作符以确定查询的输出。在一些情况下，输入查询的转换导致查询需要被应用在多个表上的集合操作符的混合。集合操作符例如包括：Union、Intersect和Except。如下面关于图5更详细地论述的，可把输入查询转换成集合操作符分析树，从中可生成谓词。

Union操作符产生组合输入查询的两个输入结果表（也被称为关系）的元组的结果集合，使得结果集合中的每个元组在任一或两个输入结果表中。该结果集合可以包括在输入结果表上查询的结果，并且还可以包括表或关系。该结果集合还可被存储在存储器122上而非数据存储器120上，如图2所示。Union操作符还将从结果集合中去除重复，而Union All操作符将保留重复。Intersect操作符取左和右结果表的元组并输出结果集合，其中，每个元组属于两个输入结果表。Intersect操作符从输入结果表中去除重复元组。在Intersect All操作符的操作下，在左结果表中具有m个重复以及在右结果表中具有n个重复的行将在输入结果表中出现min(m,n)次。Except操作符产生具有所有在第一结果表而不在第二结果表中的行的结果集合。换言之，Except操作符取一个查询的不同元组并返回不出现在第二结果表中的元组。Except All操作符将不去除重复。采用Except All，在左结果表中具有m个重复以及在右结果表中具有n个重复的行将在结果集合中呈现为max(m-n,0)次。

此外，包含在输入查询的多个结果表116中的数据例如由数据扫描模块212进行扫描。可对结果表116进行扫描以确定结果表116中的哪些包含与所接收的输入查询有关的数据。此外，可对结果表116进行扫描以确定包含在结果表116中的数据。通过特定的示例，并参照图4A，两个结果表，Table（表）I 402和Table（表）II 404由数据扫描模块212进行扫描以确定Table I包含具有名称“ABC”、“ABC”和“DEF”的数据，并且Table II 404包含具有名称“ABC”、“DEF”和“GHI”的数据。这些表402和404将以示例的方式用于描述在方法300中执行的一些操作。

在块302，在输入查询的每个输入结果表中，例如由列添加模块214来添加附加列。附加列包括在其中包含数据的输入结果表的标识符，以从而实现从中已经提取了特定数据的输入结果表的识别。在包含在数据库114中的表116（即，输入结果表）上执行的查询的结果以及附加列可被存储在存储器122中。举例来说，如图4B所示，附加列被添加到每个输入结果表402和404，并且分配给其中一个输入结果表402的标识符与分配给另一个输入结果表404的标识符不同。在图4B所描绘的示例中，Table I 402具有结果表标识符“1”而Table II 404具有结果表标识符“2”，并且表402和404可被存储在存储器122中。

在块304，例如由Union All操作执行模块216来对包含在输入结果表中的数据执行Union All操作以产生中间结果集合410（图4C）。依据示例，中间结果集合不同于输入结果表402和404，因为输入结果表402和404物理存储在磁盘（例如，数据存储器120）上，而中间结果集合410存储在存储器122中。如上面所论述的，Union All操作的执行组合两个表的元组，使得中间结果集合410（图4C）中的每个元组在任一或两个输入结果表中，同时保留两个表中的重复。图4C示出了在其中对图4B所描绘的表402和404执行Union All操作的示例。如图4C所示，Union All操作导致标记“Table I Union All Table II”的中间结果表，其包括源自Table I 402的元组和源自Table II 404的元组，以及它们各自的标识符。

在块306，例如由Group By操作执行模块218来对包含在中间结果集合中的数据执行Group By操作。一般而言，Group By操作对各组行操作并且对各组中的每一个返回一行，例如以从结果表中消除重复行。举例来说，Group By操作对一组行返回一个值，而对另一组行返回另一个值。图4D示出了在其中对图4C所示的中间结果表410执行Group By操作的示例。如图4D所示，在分组结果表420中的行已经依据包含在行中的数据的名称进行了分组，并且已经消除了重复行。

在块308，例如由聚合模块220把包含每个元组存在于多个输入结果表中的每一个中的次数的计数的聚合列添加在分组结果集合中。即，把聚合列添加到分组结果集合以识别存在于每个输入结果表中的元组的计数。依据示例，存在于每个输入结果表中的元组的计数可根据列在中间结果集合410中的标识符来确定。分组结果集合可以包括表或关系，并且可被存储在存储器122中。图4D还示出了把聚合列添加在分组结果集合420中的示例。如图4D所示，在分组结果集合420中，行已经依据包含在行中的数据的名称进行了分组，并且存在于结果Table I 402和结果Table II 404中的每一个的数据名称的计数已经被添加到聚合列中。

在块310，例如由谓词应用模块222把谓词应用在分组结果集合上以执行查询。谓词可通过实现被执行以生成谓词的操作来生成，这在本文下面进行更详细地论述。然而，一般而言，谓词可被包括在Having子句中并用于过滤由Group By子句所产生的行。通过特定的示例，并参照图4D，可生成要求存在于两个表Table I和Table II中的元组的计数大于零的谓词。在这个示例中，输出到谓词的是“ABC”和“DEF”，而“GHI”不被认为落入谓词内，并且因此不作为查询结果的一部分来输出。

虽然方法300可以在块310的执行之后结束，但还可以例如由输入/输出模块210把执行查询的结果传送到请求执行查询的客户端设备140a。

现在回到图5，示出了依据示例的用于生成谓词的方法500的流程图。谓词应用模块222或单独的模块可实现方法500。在任何方面，方法500可在集合操作符分析树中的每个节点上来实现，这可以包括查询到多个集合操作符的转换，例如，如图6中的图600所示。应当清楚理解的是，出于说明的目的并且仅作为示例来引用图6中的集合操作符分析树600，并且因此在任何方面不应被解释为本公开的限制特征。

一般而言，方法500的实现导致要被应用到以上参照图3中的块310所论述的分组结果集合上的谓词的生成。此外，谓词从包含父节点和多个定义各查询的叶节点的集合操作符分析树中生成。特别是，创建多个对应于包含在叶节点中的查询的谓词，并且依据叶节点的父节点类型创建对应于多个谓词的Predicate。即，如果父节点属于类型“Union”，那么生成Predicate以包括左子节点的谓词或右子节点的谓词；如果父节点属于类型“Intersect”，那么生成谓词以包括左子节点的谓词和右子节点的谓词；以及如果父节点属于类型“Except”，那么生成谓词以包括左子节点的谓词而不包括右子节点的谓词。方法500的描述更详细地描述了这些特征。

在块502，集合操作符分析树中的当前节点作为输入被访问。举例来说，正被访问的当前节点可以包括在图6中标记“Union”的根节点，标记“Intersect”的节点或标记“Except”的节点。依据特定示例，在块502访问的当前节点包括叶节点。

在块504，进行关于集合操作符分析树中正被访问的当前节点是否是叶节点的确定。即，进行关于当前节点是否具有子节点的确定。如果当前节点是叶节点，即，不包含子节点，那么把当前节点标记为已访问，如块506所指示的。此外，在块508，创建具有count (A)>0的谓词，其中，A是包含用于每个元组的计数器的列（例如，聚合列）。换言之，谓词从定义在当前节点的查询中被创建，其中，该查询的计数大于零。随着在块508为当前节点创建谓词，当前节点的父节点被访问，如块510所指示的。举例来说，其中，当前节点包括图6中的节点“Query（查询）1”，在块510访问的父节点包括节点“Intersect”。

此外，在块504，进行关于父节点是否包括叶节点的确定。响应于父节点不是叶节点的确定，进行关于该父节点的左子节点是否已被访问的确定，如块512处所指示的。响应于该左子节点尚未被访问的确定，在块514访问左子节点。此外，重复块504-514直到在块508为左子叶节点创建谓词。关于图6中的图600举例来说，其中，父节点是“Intersect”节点，左子节点是“Query1”节点并在块508为那个节点创建谓词。

在为左子节点创建谓词之后，父节点在块510被再次访问，并且重复块504和512。响应于在块512左子节点已被访问的确定，进行关于该父节点的右子节点在块518是否已被访问的确定。响应于该右子节点尚未被访问的确定，在块514访问右子节点。此外，重复块504-518直到在块508为右子叶节点创建谓词。关于图6中的图600举例来说，其中，父节点是“Intersect”节点，右子节点是“Query2”节点并在块508为那个节点创建谓词。

随着在块510访问回父节点以及在块512和518左和右子节点已被访问的确定，根据父节点的类型可为该父节点创建谓词。虽然接下来的操作已被描绘为按照特定次序发生，但应当清楚理解的是，在不脱离本公开的范围的情况下，接下来的操作可按任何次序执行。

在块522，可进行关于父节点（即，当前访问的节点）是否属于类型“Union”的确定。响应于该父节点属于类型“Union”的确定，在块524，创建包括左子节点的谓词 OR（或） 右子节点的谓词的谓词。然而，响应于该父节点不属于类型“Union”的确定，在块526进行关于该父节点是否属于类型“Intersect”的确定。响应于该父节点属于类型“Intersect”的确定，在块528，创建包括左子节点的谓词 AND（与） 右子节点的谓词的谓词。然而，响应于该父节点不属于类型“Intersect”的确定，在块530进行关于该父节点是否属于类型“Except”的确定。响应于该父节点属于类型“Except”的确定，在块532，创建包括左子节点的谓词 AND NOT（与非） 右子节点的谓词的谓词。然而，响应于该父节点不属于类型“Except”的确定，在块534，报告错误输出消息。例如，因为如果父节点不包括上面所论述的节点类型之一，那么存在错误条件，所以可报告错误输出消息。

在块524，528和532中的任何一个之后，在块536进行关于当前节点是否包括集合操作符分析树的根节点的确定。响应于当前访问的节点不包括根节点的确定，在块538，访问当前节点的父节点。此外，块504-538可在父节点上进行重复。响应于当前节点是根节点（即，不具有父节点）的确定，和/或如果在块534达到了错误输出条件，那么方法500可以结束，如块540处所指示的。

随着方法500在集合操作符分析树的叶节点和非叶节点上的实现，可能在块524、528和532已经创建了多个谓词。在这点上，谓词可依据更高层的父节点进行组合，其中，在块524、528和532创建的谓词在方法500的进一步迭代中变成父节点的左和右子节点的谓词。从而，最终的谓词是依据根节点的类型创建的那个。关于图6中的图600举例来说，方法500在那个图上的实现导致以下的谓词：

(count(Query1) > 0 AND count (Query2) > 0) OR (count(Query3) > 0 AND NOT (count(Query4) > 0)，其中，count(QueryN)指示元组在QueryN的输出中出现的次数。

在方法300和500中阐述的一些或全部操作可作为实用程序、程序或子程序被包含在任何所希望的计算机可访问的介质中。此外，方法300和500可由机器可读指令来体现或存储为机器可读指令，其可以各种活动和非活动二者的形式存在。例如，它们可存在为源代码、目标码、可执行代码或其他格式。以上中的任何一个可被体现或存储在非暂时性计算机可读存储介质上。非暂时性计算机可读存储介质的示例包括传统计算机系统RAM、ROM、EPROM、EEPROM以及磁性或光学盘或带。因此应当理解的是，任何能够执行上述功能的电子设备都可执行上面列举的那些功能。

现在回到图7，示出了依据示例的计算设备700的示意性表示，其可用于执行图1和2所描绘的机器110的各种功能。所述计算设备700包括处理器702，诸如但不限于中央处理单元；显示设备704，诸如但不限于监视器；网络接口708，诸如但不限于局域网LAN、无线802.11LAN、3G/4G移动WAN或WiMax WAN；以及计算机可读介质710。这些组件中的每一个都操作地耦合到总线712。例如，总线712可以是EISA、PCI、USB、火线、NuBus或PDS。

计算机可读介质710包括任何参与给处理器702提供指令用于执行的适合的介质。例如，计算机可读介质710可以是非易失性介质，诸如存储器。计算机可读介质710还可以存储操作系统714（诸如但不限于Mac OS、MS Windows、Unix或Linux）、网络应用716以及数据库管理应用718。操作系统714可以是多用户、多处理、多任务、多线程、实时等。操作系统714也可执行基本任务，诸如但不限于从输入设备（诸如但不限于键盘或小键盘）识别输入；把输出发送到显示器704；追踪介质710上的目录和文件；控制外围设备（诸如但不限于磁盘驱动器、打印机、图像捕捉设备）；以及管理总线712上的业务。网络应用716包括用于建立和维护网络连接的各种组件，诸如但不限于用于实现包括TCP/IP、HTTP、 Ethernet（以太网）、USB和FireWire（火线）的通信协议的机器可读指令。

数据库管理应用718提供用于执行如上关于图3和5中的方法300和500所论述的查询的各种组件。数据库管理应用718因此可包括输入/输出模块210、数据扫描模块212、列添加模块214、Union All操作执行模块216、Group By操作执行模块218、聚合模块220和谓词应用模块222。在这点上，数据库管理应用718可以包括用于执行方法300和500的模块。

在某些示例中，由应用718执行的一些或全部过程可被集成到操作系统714中。在某些示例中，所述过程可至少部分地在数字电子电路或计算机硬件、机器可读指令（包括固件和软件）或其任何组合中实现，同样如上面所论述的。

在本文中已经描述和说明了本公开的示例以及一些变体。在本文中使用的术语、描述和附图仅作为说明被阐述，并且不意为限制。在本公开的范围内，许多变体是可能的，这旨在由以下的权利要求——以及它们的等同物——来定义，其中，所有术语意指在它们最广泛的合理意义上，除非另有说明。