针对查询优化的范围分区统计数据的增量式维护

摘要

管理数据库中的数据的数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化的查询优化器。所述查询优化器增量式地更新所述统计数据。所述查询优化器将与数据库中的数据有关的统计数据组织成统计数据树结构，该树结构具有对应于全局统计数据的根节点、对应于子代节点的概括统计数据的内部节点、以及对应于数据库中不相交数据范围的叶节点。所述查询优化器对所述统计数据树结构执行统计数据树变换操作。所述变换操作将该统计数据树结构变换成将更新该统计数据所需的系统资源至少部分地最少化的形式。所述查询优化器更新与统计数据树结构中在不相交数据范围内发生了改变的那些节点相对应的统计数据。

说明书

背景

查询优化器被用于选择数据库查询的有效且高效的执行计划。查询优化器通常使用关于包含在数据库中的数据的统计数据。由于数据库中的数据可能会随时间改变，保持最新的统计数据很重要，使得查询优化器能够生成高效的执行计划。但是，用于更新统计数据的现有方法不允许以高效的方式来增量式地更新统计数据。

此处要求保护的主题不限于解决任何缺点或仅在诸如上述环境这样的环境中操作的各实施例。相反，提供该背景仅用于例示其中可实现所述一些实施例的一个示例性技术领域。

简要概述

管理数据库中的数据的数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化的查询优化器。所述查询优化器增量式地更新该统计数据。所述查询优化器将与数据库中的数据有关的统计数据组织成统计数据树结构，该树结构具有对应于全局统计数据的根节点、对应于子代节点的概括统计数据的内部节点、以及对应于数据库中不相交数据范围的叶节点。

所述查询优化器对所述统计数据树结构执行统计数据树变换操作。所述变换操作将该统计数据树变换成将更新该统计数据所需的系统资源至少部分地最少化的形式。所述查询优化器更新与统计数据树结构中在不相交数据范围内发生了改变的那些节点相对应的统计数据。

提供本概述以便以简化形式介绍将在以下详细描述中进一步描述的一些概念。该概述不旨在标识所要求保护的主题的关键特征或基本特征，也不旨在被用来帮助确定所要求保护的主题的范围。

附加特征和优点将在以下描述中提出，且部分会从描述中显而易见，或者可以通过实践此处的原理来获悉。本发明的特征和优点可以通过在所附权利要求书中特别指出的工具和组合来实现和获得。本发明的特征从以下描述和所附权利要求书中将更完全显而易见，或者可以通过如下文所述实践本发明而获悉。

附图简述

为了描述能够获得上述和其它优点和特征的方式，各实施例的更具体的描述将通过参考各附图来呈现。可以理解，这些附图只描绘了示例实施例，并且因此不被认为是对其范围的限制，将通过使用附图并利用附加特征和细节来描述和解释各实施例，在附图中：

图1例示出可在其中采用本文描述的一些实施例的计算系统；

图2例示出可在其中采用本文描述的一些实施例的示例数据库管理系统；

图3A例示出示例数据表分区；

图3B例示出示例统计数据树结构；

图4例示出合并一个或多个毗邻的叶节点的示例变换操作；

图5A和5B例示出基于成本函数在叶节点中重新排列物理分区的毗邻范围的示例变换操作；

图6例示出平衡统计数据树结构的示例变换操作；

图7例示出用于数据库管理系统的示例方法的流程图，数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化以增量式地更新统计数据的查询优化器；

图8例示出用于数据库管理系统的一种替代方法的流程图，数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化以增量式地更新统计数据的查询优化器；

图9例示出当对应于一个或多个叶节点的不相交数据范围已被合并时合并所述一个或多个叶节点的示例方法的流程图；

图10例示出基于成本函数在叶节点中重新排列物理分区的毗邻范围的示例方法的流程图；以及

图11例示出平衡统计数据树结构的示例方法的流程图。

详细描述

计算系统中的数据通常被储存在一个或多个数据库中。数据库是相关数据的集合。数据库中的数据通常以二维的行和列的形式(称为表)来组织。数据库通常包括多个表和多个关联结构。表是数据库中的对象，包含零个或更多记录以及在每个记录中的至少一个字段。一个记录可被具体化为表中的一行，所述记录由称为记录标识符的唯一数字标识。字段是记录的细分部分，在这个意义上，表中的一列数据代表表中的每个记录的相同字段。数据库中的一种关联结构的示例是索引，其通常但非必须地采用B树或散列索引的形式。关联结构对数据库的用户是透明的，但是对数据库管理系统的高效操作和控制来说是重要的。数据库管理系统是支持数据库特征的控制系统，数据库特征包括但不限于将数据储存在存储介质上、从存储介质检索数据、以及更新存储介质上的数据。

查询用于访问或更新数据库中的数据。查询通常以结构化查询语言(SQL)的变体来构造，该变体可以或可以不符合美国国家标准协会(ANSI)标准SQL定义。SQL查询是非程序性的，因为它以对用户有意义的语言来指定目标或期望的查询结果，但不定义查询应该被实现的步骤或过程。当一SQL查询被应用于一数据库时，该数据库管理系统的查询优化器处理该非程序化的查询以创建执行计划。执行计划是程序性的，因为它确定为实现SQL查询的目标所要执行的操作和操作符的次序和类型。非程序性查询和程序性执行计划的组合创建了查询优化器对执行计划的自动规划的机会和需求两者。查询优化器对任何给定的SQL查询可生成多个不同的执行计划，并且通常被配置为根据效率目标生成执行计划。

在很多情况下，查询优化器使用关于包含在数据库中的数据的统计数据。由于数据库中的数据可能会随时间改变，保持最新的统计数据很重要，使得查询优化器能够生成高效的执行计划。

根据本文描述的实施例，管理数据库中的数据的数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化的查询优化器。所述查询优化器增量式地更新该统计数据。所述查询优化器将与数据库中的数据有关的统计数据组织成统计数据树结构，该树结构具有对应于全局统计数据的根节点、对应于子代节点的概括统计数据的内部节点、以及对应于数据库中不相交数据范围的叶节点。

所述查询优化器对所述统计数据树执行统计数据树变换操作。所述变换操作将该统计数据树变换成减少更新该统计数据所需的系统资源的形式。

一个示例统计数据树变换操作在对应于叶节点的相邻的不相交数据范围已被合并时合并两个或更多个叶节点。例如，查询优化器确定两个相邻的不相交数据范围已被合并以创建新的不相交数据范围。查询优化器接着合并与已被合并的数据范围对应的叶节点以创建与该新的不相交数据范围的统计数据相对应的新的叶节点。在一些实施例中，查询优化器可确定要合并两个或更多个叶节点以由此引起两个或更多个相邻的或毗邻的不相交数据范围的合并。这可能会发生从而减少数据库管理系统需要维护的数据量。

另一示例统计数据树变换操作使用成本函数以在统计数据树结构的叶节点中重新排列物理分区的毗邻范围，使得叶节点有近似相等的重新计算成本。例如，查询优化器可对每个叶节点确定重新计算成本。具有高重新计算成本的叶节点被分裂成两个或更多个具有比被分裂的叶节点低的重新计算成本的叶节点。具有低重新计算成本的叶节点与其他低成本叶节点合并以创建具有比被合并的叶节点更高的重复计算成本的新的叶节点。这个过程继续直到叶节点具有近似相等的重新计算成本。

另一示例统计数据树变换操作平衡统计数据树结构以确保该统计数据树结构的高度是该树中节点数的对数。例如，查询优化器扫描该统计数据树结构的每个内部节点以确定与最优平衡的统计数据树结构相比时该内部节点是否有过多叶节点。叶节点从有过多叶节点的内部节点中被移除，并添加到有缺失叶节点的那些内部节点。

查询优化器随后可更新与统计数据树结构中在不相交数据范围内发生了足够数量的改变的那些节点相对应的统计数据。

将关于图1来阐述关于计算系统的一些引导性讨论。计算系统现在越来越多地采取多种多样的形式。例如，计算系统可以是手持式设备、电器、膝上型计算机、台式计算机、大型机、分布式计算系统或甚至常规上不被认为是计算系统的设备。在本说明书以及权利要求书中，术语“计算系统”被广义地定义为包括任何设备或系统(或其组合)，该设备或系统包含至少一个物理且有形的处理器以及其上能具有可由处理器执行的计算机可执行指令的物理且有形的存储器。存储器可以采取任何形式，并可以取决于计算系统的性质和形式。计算系统可以分布在网络环境中，并可包括多个组分计算系统。

如图1所例示，在其最基本的配置中，计算系统100通常包括至少一个处理单元102和存储器104。存储器104可以是物理系统存储器，该物理系统存储器可以是易失性的、非易失性的、或两者的某种组合。术语“存储器”也可在此用来指示诸如物理存储介质这样的非易失性大容量存储器。如果计算系统是分布式的，则处理、存储器和/或存储能力也可以是分布式的。如此处所使用的那样，术语“模块”或“组件”可以指在计算系统上执行的软件对象或例程。此处所描述的不同组件、模块、引擎以及服务可以实现为在计算系统上执行的对象或进程(例如，作为分开的线程)。

在随后的描述中，参考由一个或多个计算系统执行的动作描述了各实施例。如果这样的动作是以软件实现的，则执行动作的相关联计算系统的一个或多个处理器响应于已经执行了计算机可执行指令来引导计算系统的操作。例如，这样的计算机可执行指令可以在形成计算机程序产品的一个或多个计算机可读介质上实现。这样的操作的示例涉及对数据的操纵。计算机可执行指令(以及被操纵的数据)可以存储在计算系统100的存储器104中。计算系统100还可包含允许计算系统100例如通过网络110与其他消息处理器通信的通信信道108。

本文中描述的各实施例可包括或利用专用或通用计算机，该专用或通用计算机包括诸如例如一个或多个处理器和系统存储器等计算机硬件，如以下更详细讨论的本文中描述的各实施例还包括用于承载或存储计算机可执行指令和/或数据结构的物理和其他计算机可读介质。这样的计算机可读介质可以是可由通用或专用计算机系统访问的任何可用介质。存储计算机可执行指令的计算机可读介质是物理存储介质。承载计算机可执行指令的计算机可读介质是传输介质。由此，作为示例而非限制，本发明的各实施例可包括至少两种显著不同的计算机可读介质：计算机存储介质和传输介质。

计算机存储介质包括RAM、ROM、EEPROM、CD-ROM或其他光盘存储、磁盘存储或其他磁存储设备、或可用于存储计算机可执行指令或数据结构形式的所需程序代码装置且可由通用或专用计算机访问的任何其他物理的、有形的介质。

“网络”被定义为使得电子数据能够在计算机系统和/或模块和/或其它电子设备之间传输的一个或多个数据链路。当信息通过网络或另一个通信连接(硬连线、无线、或者硬连线或无线的组合)传输或提供给计算机时，该计算机将该连接适当地视为传输介质。传输介质可以包括可用于携带计算机可执行指令或数据结构形式的期望程序代码装置并可被通用或专用计算机访问的网络和/或数据链路。上述的组合应当也被包括在计算机可读介质的范围内。

此外，在到达各种计算机系统组件之后，计算机可执行指令或数据结构形式的程序代码资料可从传输介质自动传输到计算机存储介质(或反之亦然)。例如，通过网络或数据链路接收到的计算机可执行指令或数据结构可以在网络接口模块(例如，“NIC”)内的RAM中被缓冲，然后最终被传输至计算机系统RAM和/或计算机系统处的较不易失性的计算机存储介质。因而，应当理解，计算机存储介质可被包括在还利用(或甚至主要利用)传输介质的计算机系统组件中。

计算机可执行指令例如包括，当在处理器处执行时使通用计算机、专用计算机、或专用处理设备执行某一功能或某组功能的指令和数据。计算机可执行指令可以是例如二进制代码、诸如汇编语言之类的中间格式指令、或甚至源代码。尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所附权利要求书中定义的主题不必限于上述特征或动作。相反，上述特征和动作是作为实现权利要求的示例形式而公开的。

本领域的技术人员将理解，本发明可以在具有许多类型的计算机系统配置的网络计算环境中实践，这些计算机系统配置包括个人计算机、台式计算机、膝上型计算机、消息处理器、手持式设备、多处理器系统、基于微处理器的或可编程消费电子设备、网络PC、小型计算机、大型计算机、移动电话、PDA、寻呼机、路由器、交换机等等。本发明也可在其中通过网络链接(或者通过硬连线数据链路、无线数据链路，或者通过硬连线和无线数据链路的组合)的本地和远程计算机系统两者都执行任务的分布式系统环境中实施。在分布式系统环境中，程序模块可以位于本地和远程存储器存储设备二者中。

现在注意图2，图2例示出本文中公开的实施例可在其中实施的示例数据库管理系统200。所述数据库管理系统可在图1中的计算系统中被实现。将理解，图2的数据库管理系统200仅为一个示例。因此，所述数据库管理系统200可包括比图2中所示的元素更多或更少的元素。还将理解，数据库管理系统200的元素可位于单个计算系统上或可跨多个计算系统分布。此外，图2中所示的数据库管理系统200的元素可视情况被组合。

在操作中，数据库管理系统200被配置为促进对存储在数据库210中的数据的访问，数据库210可为关系数据库。如所例示，数据库210包括各种数据表215。图2示出数据表215A、数据表215B、以及数据表215C。省略号215D说明可以有任意数量的附加数据表215，对大数据库210而言，该数量可为数千和数万。当然，可能存在少于三个数据表215。尽管没有示出，数据表215通常被组织成列和行，数据字段位于列和行的交叉处。

一般而言，被组织成存储在数据库210中的数据表215的数据是通过用户定义的查询205来被访问的，该用户定义的查询以诸如结构化查询语言(SQL)的查询语言构造。通常，对于任何给定的SQL查询，存在需要对数据执行的许多程序性操作，以便实现该SQL查询的目标。例如，可能存在需要被执行以完成期望的目标的许多联接以及表扫描。这些表联接和扫描通常可按各种不同的顺序被执行而达到相同的结果。完成期望的目标的程序性操作的组合被称为“执行计划”。可能存在可针对任一个SQL查询205开发的许多执行计划。

数据库管理系统200通常自动从可能针对SQL查询205而存在的许多执行计划中挑选一个执行计划来实现。用于选择执行计划的一个常用准则是挑选提供最高效率的计划，即涉及对系统资源(诸如处理周期和逻辑I/O)的最少使用。一般而言，需要处理数据表215中最小数量的行的计划也使用最少的系统资源。因此，用于挑选最高效的执行计划的一个关键原则是挑选使数据表215的需要被处理的行数最小化的计划。

因此，数据库管理系统200包括查询优化器220。在操作中，查询优化器220标识将对于查询205来说是最高效的执行计划。这种标识通常依赖于关于数据表215的各种统计数据216。

如图所示，数据管理系统200包括统计数据存储库211或能够访问统计数据存储库211。在一些实施例中，统计数据存储库211可能为数据库210的一部分，而在其他实施例中，统计数据存储库211可能为一分离的数据库或其他持久存储器。

统计数据存储库211存储或以其他方式持久保持各种统计数据216。图2示出统计数据216A、统计数据216B、以及统计数据216C。省略号216D说明可存在任意数量的附加统计数据。当然，可能存在少于三个统计数据216。

统计数据216包括关于数据表215的信息218。信息218可以是关于所述数据表215的任何期望的信息。信息218可包括但不限于：存储列的数据表215中的行数；存储在一列中的数据所占用的近似页数；存储在该列中的数据的平均长度；该列中值的分布(例如，直方图)；该列中值的密度；以及用来产生直方图和密度信息的列值数量。

如将理解的，知道统计数据216上次何时被更新通常是合乎需要的。因此，信息218也可包括关于统计数据216上次何时被更新的信息。以此方式，查询优化器220能够确定统计数据216有多新(即，更新有多近)。

在一些实施例中，统计数据216可包括计数器217。计数器217可被用来确定以对与统计数据216对应的底层数据表215作出改变的次数。即，每一次对数据表215作出改变，计数器217递增。这也允许查询优化器220确定统计数据216有多新。在以下更详细解释的一实施例中，计数器217被用作确定是否需要任何统计数据更新的阈值分析的一部分。

如将理解的，当统计数据216被查询优化器220用来标识最高效的执行计划时，统计数据216足够新是必要的。如果统计数据216不足够新，则它们提供给查询优化器220的关于数据表215的信息可能是过时的，这可能导致对低效执行计划的选择。

然而，也将理解，更新统计数据216需要系统资源。如果有大量的统计数据216，则更新统计数据所需的资源量(在本文中也被称为更新成本或重新计算成本)可能比进行没有执行计划的查询搜索更高。因此，本文公开的实施例提供了允许仅对相关的或相应的数据表215自上次更新后已作了足够的改变以证明有更新资格的那些统计数据进行增量式更新或重新计算的系统和方法。

查询优化器220或数据库管理系统200的某一其他部分包括统计数据树组织模块230。在操作中，如将在以下更详细解释的，统计数据树组织模块230将一个或多个数据表215的统计数据216或一个或多个数据表215的特定分区的统计数据216组织为特定的统计数据树结构234，该统计数据树结构234允许各种统计数据树变换操作被执行，从而使更新所述统计数据216所需的系统资源最少化。

在一个实施例中，当查询优化器220接收到查询205时，查询优化器可访问统计数据存储库211以确定任何现有的统计数据216是否是数据表215的匹配所述查询205的统计数据。如果为是，则这些现有的统计数据可被组织成统计数据树结构234。如果不存在任何现有的统计数据或如果仅存在一些现有的统计数据，则查询优化器220可生成所需的统计数据216并随后将生成的统计数据或生成的和现有的统计数据的组合组织成统计数据树结构234。

在一些实施例中，统计数据树结构234具有指定可被包括在统计数据树结构234中的节点数的树参数235。在一个实施例中，树参数235可包括指定每个内部节点的子节点的最大数目的参数CPN。树参数235也可包括指定整个统计数据树结构的叶节点的最大数目的参数LC。在一个实施例中，CPN可等于2，而LC可等于1000。

树参数235是基于数据库管理系统200和/或查询优化器220的底层系统资源被确定的。例如，如将在以下更详细解释的，数据库管理系统200和/或查询优化器220将实现合并节点的合并功能以及重采样统计数据的重采样功能。被数据库管理系统200和/或查询优化器220所使用的特定的合并功能和重采样功能对于在本文中公开的实施例并不重要，因为任何合理的合并功能和/或任何合理的重采样功能都可被使用。但是，合并功能和/或任何重采样功能的类型可帮助确定树参数235。

例如，若实现的合并功能次线性地缩放，则CPN可被选得高。若实现的合并功能超线性地缩放，则CPN可被选得低。同样，若实现的合并功能是潜在有损耗的，则选择较高的CPN可减少损耗量。LC是基于创建的性能准则被选择的。只要数据表215扫描的成本比合并的成本高得多，则LC越大，增量式更新越快且初始创建越慢。

现在注意图3A和3B，图3A和3B例示出根据本文中公开的实施例的统计数据树结构234的示例组织。图3A例示出示例数据表分区310。数据表分区310可为数据表215之一的分区。如所例示，底层数据表215的行、列和其他数据没有被包括，使得重点可放在数据表的分区上。将理解，就分区键而言，本文中使用的分区旨在至少意味着数据表如何被分成不同的、独立的部分。在一些实施例中，分区被定义为数据库表的单列。

数据表分区310包括对应于由“1”标识的第一分区的第一不相交数据范围301。第一不相交数据范围301包括最小边界341和最大边界342。第二不相交数据范围302对应于由“2”标识的第二分区。第二不相交数据范围302与第一不相交数据范围301共享边界342作为最小边界，且有最大边界343。第三不相交数据范围303对应于由“3”标识的第三分区。第三不相交数据范围303与第二不相交数据范围302共享边界343作为最小边界，且有最大边界344。第四不相交数据范围304对应于由“4”标识的第四分区。第四不相交数据范围304与第三不相交数据范围303共享边界344作为最小边界，且有最大边界345。第五不相交数据范围305对应于由“5”标识的第五分区。第五不相交数据范围305与第四不相交数据范围304共享边界345作为最小边界，且有最大边界346。第六不相交数据范围306对应于由“6”标识的第六分区。第六不相交数据范围306与第五不相交数据范围305共享边界346作为最小边界，且有最大边界347。将理解，数据范围301至306是不相交数据范围，因为它们没有重叠数据。

数据表分区310也示出每个所述分区的对应的统计数据，统计数据可对应于所述统计数据216之一。例如，统计数据311对应于分区1，统计数据312对应于分区2，统计数据313对应于分区3，统计数据314对应于分区4，统计数据315对应于分区5，而统计数据316对应于分区6。这些统计数据可为先前生成并存储在统计数据存储库211中的统计数据，或它们可在组织时被生成。将理解，统计数据311-316通常不会是数据表分区310的底层数据表215的一部分。然而，统计数据311-316被包括在此，以在示出哪一统计数据对应于哪一分区时便于说明。

转向图3B，例示出对应于统计数据树结构234的统计数据树结构320。统计数据树结构320例示出图3A所示的分区的一对一映射。这样做是为了便于说明。然而将理解，统计数据树结构320无须是一对一映射，因为毗邻分区的其他有效映射也是可能的。

统计数据树结构320包括根节点321。根节点321对应于全局统计数据331。全局统计数据331包括如由{1…6}所例示出的分区1-6的所有统计数据的不相交并集。

统计数据树320包括也是所述根节点321的子节点的两个内部节点322和323。内部节点322对应于增量式概括统计数据332。增量式概括统计数据332包括如由{1,2,3}所例示出的毗邻分区1、2和3的所有统计数据的不相交并集。内部节点323对应于增量式概括统计数据333。增量式概括统计数据333包括如由{4,5,6}所例示出的毗邻分区4、5和6的所有统计数据的不相交并集。

统计数据树结构320包括6个叶节点324-329。叶节点324-326是内部节点322的子节点，而叶节点327-329是内部节点323的子节点。叶节点324对应于分区1的统计数据311，叶节点325对应于分区2的统计数据312，叶节点326对应于分区3的统计数据313，叶节点327对应于分区4的统计数据314，叶节点328对应于分区5的统计数据315，而叶节点329对应于分区6的统计数据316。

将理解，统计数据树结构320基于不相交数据范围301-306而非分区范围。即，分区的边界341-347是由数据范围定义的。因此，这意味着统计数据树结构320(以及对应的统计数据树结构234)可独立于底层数据表215的模式(schema)。然而，在一些实施例中，数据库管理系统可强制实施与底层数据表215的模式有关的某些规则，例如叶节点在合并后必须只覆盖完整分区。

如上所述，统计数据树结构320可具有指定可被包括在统计数据树结构320中的节点数的相关联的树参数235。将理解，统计数据树结构320可至少具有为3的CPN和为6的LC，因为每个内部节点322和323有3个子节点，以及总共存在6个叶节点324-329。

回到图2，查询优化器220包括统计数据树变换模块240。在操作中，统计数据树变换模块240对统计数据树结构234执行各种变换操作。这些变换操作将统计数据树结构234变换成至少部分地将更新与统计数据树结构234的节点对应的统计数据216所需的系统资源最少化的形式。替代地，变换操作在数据表的数据301-306的至少一个不相交数据范围被改变时，变换统计数据树结构234。现在将解释变换操作的示例。

注意图4，图4例示出当对应于叶节点的毗邻不相交数据范围已被合并时，合并一个或多个叶节点的变换操作。图4例示出数据分区表410，数据分区表410是关于图3讨论的数据分区表310的合并版本。如所示，数据分区表410示出对应于分区1,2的第一数据范围401，第一数据范围401代表数据分区表310的分区1和2的物理合并。即，分区1和2中的数据已被合并以形成单个数据范围401和分区。换言之，底层数据表215中的数据已被合并使得分区1的最大边界和分区2的最小边界不再是边界342。相反，合并分区的最小边界现在是边界341而最大边界是边界343。即，边界342不再是分区1和2的有效边界，因为边界342不再是底层数据表的分区之间边界的子集的一部分。

数据分区表410还示出对应于分区4,5的第二数据范围402，第二数据范围402代表数据分区表310的分区4和5的合并。即，分区4和5中的数据已被合并以形成单个数据范围402和分区。换言之，底层数据表215中的数据已被合并使得分区4的最大边界和分区5的最小边界不再是边界345。相反，合并分区的最小边界现在是边界344而最大边界是边界346。即边界345不再是分区4和5的有效边界，因为边界345不再是底层数据表的分区之间边界的子集的一部分。

统计数据411对应于统计数据311和312的不相交并集或合并。统计数据412对应于统计数据314和315的不相交并集或合并。分区3和6以及它们对应的统计数据313和316与数据分区表310并无不同，因为这些分区不变。

图4还示出由变换操作从统计数据树结构320变换来的统计数据树结构420，该变换操作在对应于叶节点的不相交数据范围已被合并时合并一个或多个叶节点。如所示，统计数据树结构420包括先前所讨论的根节点321以及两个内部节点322和323。这些节点是不变的，因为合并仅影响了子代节点，且因此对应于这些节点的统计数据无需改变。此外，图4示出叶节点326和329与统计数据树结构320并无不同。

然而，统计数据树结构420具有新叶节点424，新叶节点424是内部节点322的子节点。叶节点424对应于合并的毗邻分区1,2的合并统计数据411。统计数据树结构420还包括另一新叶节点426，新叶节点426是内部节点323的子节点。叶节点426对应于合并的毗邻分区4,5的合并统计数据412。因此，此变换操作确保统计数据树结构234以及因此对应的统计数据216与底层数据表215的实际分区相匹配。

将理解，尽管关于图4所描述的实施例示出统计数据树结构420取决于数据表410，这仅是为了便于说明且不必如此。在一些实施例中，查询优化器可确定要合并两个或更多个叶节点以由此引起两个或更多个毗邻的不相交数据范围的合并。

此外，可能存在物理分区中的变化没有引起统计数据树结构的相应变化或统计数据树结构中的变化没有引起物理分区中的变化的情况。例如，若某一叶节点包括分区1,2且随后此分区被划分成了分区1和分区2，则可能没有对统计数据树结构的任何改变，因为包括分区1,2的叶节点已经包括了这些分区的数据范围的最小边界和最大边界。换言之，分区1和分区2的最小和最大数据范围边界是分区1,2的数据范围边界的子集。因此，物理分区与对应的统计数据树结构取决于数据表的底层数据范围。

回到图2，统计数据树变换模块240可包括成本函数245或能访问成本函数245，成本函数245由变换操作用来在叶节点中混洗分区，从而优化统计数据树结构的叶节点的数目，使得叶节点对于它们的对应的统计数据将具有近似相等的重新计算成本。如将理解的，每个节点的重新计算成本可能不相等。例如，一些节点可能具有对应于它们的统计数据的较大量的数据，而其他节点可能具有较长时间段内没被更新的统计数据。因此，统计数据树变换模块240可使用成本函数240以确定统计数据树结构234的每个叶节点的重新计算成本。叶节点的数目和排列可随后被优化以使得每个叶节点的重新计算成本在实现指定的重新计算成本是可接受的那些实施例中近似相等或充分相等。将理解，叶节点的经优化的数目和排列不可违反参数CPN和LC(或任何其他参数235)。将理解，本文所使用的重新计算成本可指节点的初始重新计算成本，也可指基于节点被更新的概率的估计的未来重新计算成本，或这两者的任何结合。

在一个实施例中，成本函数245是N+kT，其中N是底层数据表215的行数或其他数据，T是自从上一次统计数据更新后底层数据表215的数据的改变次数，k是基于数据管理系统200资源的常数。在此成本函数中，N与重新计算成本成比例，因为对于统计数据更新而言，越大数量的行或数据通常会消耗越多的资源。T的值与将对给定分区发生更新的概率有关，因为从上次更新以来经过的时间越长，将越可能发生更新。在一些实施例中，T的值可由先前所述的计数器217确定。低k值将尝试使未来的重新计算成本最小化，而高k将尝试使需要发生任何更新的概率最小化。

现在注意图5A，图5A例示出在统计数据树结构的叶节点中混洗分区使得叶节点将具有近似或充分相等的重新计算成本的变换功能的实施例。图5示出统计数据树结构510，统计数据树510可对应于先前讨论的在应用了成本函数245之前的统计数据树234或320。统计数据树结构510包括根节点501、内部节点502和503、以及如先前所讨论的分别与底层数据表215的分区1-6相关的叶节点504-509。

在操作中，成本函数245被应用于统计数据树结构510以确定每个节点的重新计算成本。随后查询优化器220作出确定：叶节点的重新计算成本是高成本还是低成本。如果重新计算成本是低成本，则该叶节点可与一个或多个其他低成本叶节点合并以创建新叶节点，该新叶节点具有比被合并以创建该新叶节点的节点更高的重新计算成本。如果该叶节点的重新计算成本是高成本，则该节点可被分成两个或更多个叶节点，每个叶节点具有比被分裂以创建它们的所述叶节点更低的重新计算成本。

假定由于底层数据表的分区中的改变或某种其他原因(诸如用户决定或可用系统资源)，查询优化器确定统计数据树结构510现仅能支持5个叶节点。在此情况下，叶节点中的两个将需要合并为单个叶节点使得仅5个叶节点被使用。如将理解的，节点504和505可被合并，节点505和506可被合并，节点506和507可被合并，节点507和508可被合并，以及节点508和509可被合并。

为了确定哪两个节点应被合并，如先前所述，每个节点的重新计算成本被确定。图5A是示出节点505和506被发现具有最低重新计算成本且因此被合并为在510处示出的新节点的图示。因此，统计数据树结构510现在具有5个叶节点。

将理解，为达到允许的5个叶节点，节点505和506的合并可被改变。例如，假定大量数据被添加至对应于底层数据表中的节点505和506的分区2和3中。在这种情况下，查询优化器220可确定节点505和506不再应该被合并，且两个其他节点应被合并以达到5个允许的叶节点。因此，节点510可被分裂回个体节点505和506。另外，除节点505和506之外的具有最低重新计算成本的两个节点可被确定且随后被合并使得保持5个叶节点。

假定查询优化器220后来确定可支持6个叶节点。在这种情况下，对于图5A的示例，叶节点510将被分裂回节点505和506。但是，如果系统确定附加叶节点可被支持，则查询优化器220可分裂附加叶节点。例如，假定统计数据树210的LC至少为7。在这种情况下，每个节点的重新计算成本会被确定，且具有最高成本的节点会被分裂以创建具有较低重新计算成本的至少两个节点。图5B示出节点509已被分裂成两个较低成本的节点511和512，使得存在7个叶节点。

将理解，图5A和图5B的图示已被简化以示出底层变换操作。然而，在很多实施例中，在叶节点中重新混洗分区时，可能发生合并和分裂的组合。另外，合并和分裂无需为二对一合并或一对二分裂。例如，在存在7个分区但仅允许5个叶节点的实施例中，系统可合并两对节点以达到5个叶节点，或可将3个叶节点合并为单个叶节点。两者都将是从7个叶节点到5个叶节点的有效方法。

在一个实施例中，确定每个叶节点的重新计算成本以及随后合并低成本节点和分裂高成本节点的过程将继续，直到到达一固定点为止，在该固定点，所有叶节点具有在给定统计数据树结构的CPN和LC的情况下尽可能接近相等的重新计算成本。换言之，系统将继续基于重新计算成本合并和分裂直到存在具有近似相等的重新计算成本但不超过统计数据树结构的CPN和LC的可能最大数目的叶节点。以此方式，使统计数据树结构形成当更新统计数据216时将至少部分地最少化资源成本的形式，因为节点以至少近似地使重新计算成本相等的方式被排列。如所述，在一些实施例中，所述过程将继续直到叶节点的重新计算成本充分相等。

回到图2，统计数据树变换模块240还可执行通过平衡统计数据树结构234而使执行更新所需的资源最少化的变换操作。在一个实施例中，该变换操作确保统计数据树234的高度保持为树中节点数目的对数，从而防止长而细的树。另外，该变换操作尝试平衡统计数据树结构的叶节点从而使重新计算任何内部节点或根节点的需求最小化。即，叶节点绕内部节点以尝试防止对各种子树的根节点或其他节点的任何改变的方式被移动。

在一个实施例中，进行平衡变换操作，将统计数据树结构234变换成最优平衡的统计数据树结构246。最优平衡的统计数据树结构246被定义为对于统计数据树结构234的给定的CPN和LC具有平衡的对数高度的统计数据树。

图6示出平衡变换操作的一个实施例。如所例示，图6示出包括一根节点和各种内部节点以及叶节点的统计数据树结构610。如所例示，统计数据树结构610的高度不是针对该树的节点数目进行对数平衡的，因为它是长且细瘦的。

在平衡变换操作期间，如果与最优平衡的统计数据树结构246相比某一节点有过多的子节点，这些子节点就会被添加至队列620，队列620可为任何合理的存储器或缓存器。队列620中的子节点可随后被添加至与最优平衡的统计数据树结构246相比时具有缺失的子节点的那些节点。此过程根据需要被重复，直到在给定统计数据树结构的CPN和LC的情况下，统计数据树610具有针对统计数据树的节点数目进行了对数平衡的高度。这在图6中被例示为统计数据树结构630。

回到图2，查询优化器具有统计数据更新模块250，统计数据更新模块250执行统计数据216的任何所需的更新。在一个实施例中，更新策略255被用来确定哪些统计数据需要被更新。例如，统计数据树结构234的深度优先遍历可被执行以确定哪些叶节点需要重编以基于策略255更新统计数据。由于各种变换操作已如所述地变换了统计数据树结构，因此底层数据表215中数据已被改变了的那些统计数据将被更新，而无改变的那些统计数据不会被更新。换言之，增量式更新会仅对其中发生了改变的那些统计数据发生。另外，变换将使更新确实发生时所需的资源最少化。

例如，如果变换操作改变了数据表215的不相交数据范围，则更新将发生。如果一子节点被标记来更新，则相对应的内部节点也将被更新。如果变换操作不导致对统计数据树结构234的改变，这意味着不需要更新。有利地，统计数据树结构234允许每个内部节点的叶节点数目增加，并且这允许对各子树的平行更新而无需更新未受影响的子树。

一旦完成了增量式统计数据更新，查询优化器220便可使用更新后的统计数据来确定查询205的高效执行计划。从增量式更新发生以来，统计数据216将足够新。

在一些实施例中，查询优化器220可包括阈值模块260。在操作中，阈值模块260访问阈值265。阈值265定义在任何统计数据216更新需要发生之前数据表215的数据需要被改变的最小量。换言之，阈值模块260担当确定是否数据中发生了足够的改变的把关者，以证明继续进行增量式统计数据更新所需的资源合法。在改变超过阈值265之前，由于统计数据216被视为足够新以允许选择高效执行计划，因此将不发生更新。

在一个实施例中，阈值模块260将阈值265与先前所述的计数器217相比较。当计数器217指示出阈值265已被超过时，阈值模块260通知查询优化器220统计数据216可被组织成统计数据树结构234且变换操作如先前所述那样被执行。

下面的讨论现在涉及可被执行的多个方法和方法动作。尽管这些方法动作可以以特定次序被讨论或在流程图中被例示为以特定次序发生，但是除非特别指明否则不需要任何特定排序，或者因某一动作取决于在该动作被执行之前完成的另一个动作而要求特定排序。

图7例示出用于数据库管理系统的示例方法700的流程图，数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化以增量式地更新统计数据的查询优化器。将参考上文所述的数据库管理系统200来描述方法700。

方法700包括将与数据库中的数据有关的统计数据组织成统计数据树结构的动作(动作710)。数据树结构具有对应于一个或多个全局统计数据的根节点、对应于子代节点的增量式概括统计数据的一个或多个内部节点、以及对应于与数据库中的不相交数据范围有关的一个或多个统计数据的一个或多个叶节点。例如，统计数据树组织模块230可将统计数据216组织成统计数据树结构234。如关于图3B所描述的，对应于统计数据树结构234的统计数据树结构320可具有对应于全局统计数据331的根节点321和对应于增量式概括统计数据322和333的内部节点322和323。统计数据树结构320还可具有对应于与底层数据表215的分区310的不相交数据范围有关的统计数据311-316的叶节点324-329。在一些实施例中，在组织统计数据树结构之前，阈值模块260确定统计数据216是否改变得足以证明有资格进行任何更新。

方法700包括执行一个或多个统计数据树变换操作的动作，变换操作将统计数据树结构变换成至少部分地将更新对应于一个或多个节点的统计数据所需的系统资源最少化的形式(动作720)。例如，统计数据树变换模块240对统计数据树结构234执行统计数据树变换操作以如先前所述那样变换统计数据树结构。统计数据树变换操作可按照关于上文所述的图4至图6描述的变换操作。

方法700包括更新与统计数据树结构中已发生对数据库的数据的不相交范围的改变的那些节点对应的统计数据的动作(动作730)。例如，统计数据更新模块250可以先前所述的方式更新对应于统计数据树结构234的统计数据216。

图8示出了用于数据库管理系统的示例方法800的流程图，数据库管理系统包括基于与数据库中的数据有关的统计数据执行查询优化以增量式地更新统计数据的查询优化器。将参考上文所述的数据库管理系统200来描述方法800。

方法800包括将与数据库中的数据有关的统计数据组织成统计数据树结构的动作(动作810)。数据树结构具有对应于一个或多个全局统计数据的根节点、对应于子代节点的增量式概括统计数据的一个或多个内部节点、以及对应于与数据库中的不相交数据范围有关的一个或多个统计数据的一个或多个叶节点。例如，统计数据树组织模块230可将统计数据216组织成统计数据树结构234。如关于图3B所描述的，对应于统计数据树结构234的统计数据树结构320可具有对应于全局统计数据331的根节点321和对应于增量式概括统计数据322和333的内部节点322和323。统计数据树结构320还可具有对应于与底层数据表215的分区310的不相交数据范围有关的统计数据311-316的叶节点324-329。在一些实施例中，在组织统计数据树结构之前，阈值模块260确定统计数据216是否改变得足以证明有资格进行任何更新。

方法800包括当对应于一个或多个叶节点的毗邻的不相交数据范围已被合并时合并所述一个或多个叶节点的动作(动作820)。动作820的示例将关于如图9所例示当对应于一个或多个叶节点的不相交数据范围已被合并时合并所述一个或多个叶节点的方法900被描述。

方法900包括确定数据库的第一不相交数据范围已与数据库的第二毗邻的不相交数据范围合并从而创建数据库的第三不相交数据范围的动作(动作910)。例如，如图3和图4所示，对应于分区1和分区2的毗邻的不相交数据范围301和302被合并以创建对应于分区1,2的新的不相交数据范围401。同样地，对应于分区4和分区5的毗邻的不相交数据范围304和305被合并以创建对应于分区4,5的新的不相交数据范围402。

方法900包括将对应于第一不相交数据范围的第一叶节点和对应于第二不相交数据范围的第二叶节点合并从而创建对应于与第三不相交数据范围有关的一个或多个统计数据的第三叶节点的动作(动作920)。例如，如图3和图4所示，叶节点324和325被合并以创建新叶节点424，新叶节点424对应于作为统计数据311和312的合并结果的统计数据411。同样地，叶节点327和328被合并以创建新叶节点426，新叶节点426对应于作为统计数据314和315的合并结果的统计数据412。

回到方法800，方法800还包括基于成本函数在叶节点中重新排列物理分区的毗邻范围的动作(动作830)。动作830的示例将关于如图10所例示的基于成本函数重新排列叶节点的方法1000来被描述。

方法1000包括基于成本函数确定用于更新统计数据树结构的每个对应的叶节点的统计数据的重新计算成本的动作(动作1010)。例如，成本函数245可被应用于统计数据树结构234的叶节点以如上所述确定每个叶节点的重新计算成本。在一个实施例中，成本函数可为N+kT，其中N为数据库中对应于叶节点的不相交数据范围中的行数，T为从上一次统计数据更新后数据库中不相交数据范围的改变次数，k是基于系统资源的常数。

方法1000包括将具有高重新计算成本的叶节点分裂成各自具有比被分裂的叶节点更低的重新计算成本的两个或更多个叶节点的动作(动作1020)。例如，如图5B所示，叶节点509可具有高重新计算成本。因此，叶节点509被分裂成各自具有比叶节点509更低的重新计算成本的叶节点511和叶节点512。

方法1000包括将具有低重新计算成本的两个或更多个叶节点合并成具有比被合并的叶节点更高的重新计算成本的新的单个叶节点的动作(动作1030)。例如，如图5A所示，叶节点505和506可具有低重新计算成本。因此，这些叶节点被合并以创建具有比叶节点505和506更高的重新计算成本的新叶节点510。

方法1000包括继续分裂和合并动作直到叶节点的数目达到子节点的最大数目，且所述最大数目的叶节点被生成具有近似相等的重新计算成本的动作(动作1040)。例如，分裂和合并的过程被继续直到不违反统计数据树结构的CPN和LC的数量的叶节点被形成，这些叶节点具有近似相等的重新计算成本，如先前所述。

回到方法800，方法800包括基于成本函数对统计数据树结构的节点进行对数平衡的动作(动作840)。动作840的示例将关于如图11所例示的平衡统计数据树结构的叶节点的方法1100来被描述。

方法1100包括扫描每个节点以确定与对于最大子节点数和最大叶节点数具有最优对数平衡高度的统计数据树结构相比节点是否具有过多的子节点的动作(动作1110)。例如，如先前所述，查询优化器可扫描统计数据树结构234的节点以确定与对于统计数据树结构234的给定的CPN和LC的最优平衡的统计数据树结构246相比时的过多的子节点。

方法1100包括将任何过多的子节点从具有过多的子节点的那些节点移除并将所述过多的子节点置于队列中的动作(动作1120)。例如，如图6所示，统计数据树结构610的任何过多的子节点被置于队列620中。

方法1100包括将来自所述队列的子节点添加至不具有过多的子节点的那些节点的动作(动作1130)。例如，如图6所示，来自队列630的过多的子节点被添加至统计数据树结构630从而对统计数据树结构630的高度进行对数平衡。

回到方法800，方法800包括更新与统计数据树结构中已发生对数据库的不相交数据范围的改变的那些节点相对应的统计数据的动作(动作850)。例如，统计数据更新模块250可用先前所述的方式更新与统计数据树结构234对应的统计数据216。

本发明可具体化为其它具体形式而不背离其精神或本质特征。所描述的实施例在所有方面都应被认为仅是说明性而非限制性的。从而，本发明的范围由所附权利要求书而非前述描述指示。落入权利要求书的等效方案的含义和范围内的所有改变应被权利要求书的范围所涵盖。