用于OLTP和分析工作量的用于内存数据库的组合行和列式存储

摘要

表的列按行为主的格式或列为主的格式存储在内存DBMS中。对于给定的表，一组列按列为主的格式存储；表的另一组列按行为主的格式存储。存储表的列的这种方式在本文中被称为双主格式。此外，双主表中的行被“就地”更新，即，更新是直接对列为主的列进行的，而无需创建该行的列为主的列的临时行为主形式。用户可以提交声明表的行为主的列和列为主的列的数据库定义语言(“DDL”)命令。

说明书

技术领域

本发明涉及数据库管理系统(DBMS)，并且更具体而言，涉及DBMS中数据库的列式存储。

背景技术

DBMS以若干种存储格式存储数据库数据。这些包括行为主的格式、列为主的格式，以及混合列式格式。在行为主的格式中，单行的列值被连续存储在存储器单元(诸如数据块)内的地址空间中。在列为主的格式中，多行的一列的值被连续存储在存储器单元内的地址空间中。在混合列式格式中，一组行的全部被包含在持久性存储器单元(诸如数据块)当中。但是，在存储器单元中，至少该组行的子集按列为主的格式被存储。

行为主的格式对涉及随机访问模式的工作量提供高性能，诸如索引表查找以及涉及更细粒度的访问行级更新的数据的频繁更新。行为主的格式对于列式扫描不是最佳的，因为扫描涉及读取行的不是列式扫描操作的对象的许多列。

列为主的格式对于列式扫描是有效的，因为可以在不读取与列式扫描操作不相关的其它列的情况下读取单个列。各种硬件加速技术(诸如预取出和面向向量的执行)可被用来加速列式扫描操作。此外，列为主的格式允许更好的压缩性。一列中的值可以具有共同的属性，使得当连续存储所述值时可以使用各种压缩技术利用共同的属性。

另一方面，列为主的格式具有更新低效的缺点；对列的更新需要对列进行显著的重新组织。一般而言，在列为主的数据被更新的方法中，对列的改变首先被临时进行(stage)，然后合并到列为主的数据中，这通常脱机按批进行。

更新列为主的数据的一种方法是优先行拷贝的更新。在优先行拷贝的更新下，维护了数据库的两个完整版本，一个是列为主的格式，一个是行为主的格式。更新对行为主的拷贝进行，随后按批应用到列为主的拷贝。这些方法需要当进行改变时和当改变可以被对照列为主的版本计算的查询看到时之间的存储开销和延迟。

另一种方法是改变-内联方法，该方法用于按混合列式格式存储的数据。混合列式格式被设计为在一定程度上实现行为主和列为主的格式二者的好处，同时减轻列为主的格式的缺点，所述缺点包括对于更新的缺点。对一组行的更新的影响局限于存储该组行的数据块。

但是，对数据块中行的列的更新需要将该行在数据块内转换成行为主的格式、更新该行并且在数据块内将该行保持为行为主的格式。最终，转换后的行可以在数据块中被转换回列为主的格式。这种方法需要将行转换成行为主的格式以及处理计算对以列为主的格式和行为主的格式二者存储行的数据块的查询的复杂性的开销。

附图说明

图1是绘出根据本发明实施例的用于存储双主数据的列分区和行分区的图。

图2是绘出根据本发明实施例的行页面和列页面的图。

图3是绘出根据本发明实施例的用于对列页面进行列式扫描的过程的流程图。

图4是绘出根据本发明实施例的就地更新的流程图。

图5是绘出根据本发明实施例的在利用行程长度编码压缩的列分区上的位置索引的图。

图6是绘出可以在本发明实施例中使用的计算机系统的图。

具体实施方式

在以下描述中，出于解释的目的，阐述了许多具体细节，以便提供对本发明的透彻理解。但是，很显然，本发明可以在没有这些具体细节的情况下进行实践。在其它情况下，众所周知的结构和设备以框图的形式示出，以避免不必要地模糊本发明。

总体概述

本文描述的是用于在内存DBMS中按行为主的格式或列为主的格式存储表的列的方法。对于给定的表，一组列按列为主的格式存储；该表的另一组列按行为主的格式存储。这种存储表的列的方式在本文中被称为双主格式。通过内存DBMS管理、处理和存储内存双主数据库在本文中被称为双重内存存储。

此外，双主表中的行是“就地”更新的，即，更新是直接对列为主的列进行的，而无需创建该行的列为主的列的临时行为主形式。根据标准的事务处理协议，在数据库事务提交更新后，改变立即对DBMS的数据库事务可见。

用户可以提交声明表的行为主的列和列为主的列的数据库定义语言(“DDL”)命令。因此，数据库可被设计成对同一个表利用行为主和列为主的格式二者的优势。列的存储格式可以按照对该列的预期访问模式来选择和优化。

内存双主数据库

根据本发明的实施例，内存DBMS在内存双主数据库中管理、处理和存储数据。在内存DBMS中，DBMS管理主要存储在随机存取存储器(RAM)中的数据库。其中存储数据库的RAM可以仅包括易失性RAM、非易失性RAM(例如PRAM)，或两者的组合。内存DBMS的例子在(1)于2010年3月8日由SouravGhosh等人提交且标题为“AutomatedIntegratedHighAvailabilityOfTheIn-MemoryDatabaseCacheandtheBackendEnterpriseDatabase”的美国专利申请号12/719,264，和(2)于2008年2月12日由RohanAranha提交且标题为“DatabaseSystemwithActiveStandbyandNodes”的美国专利申请12/030,094中描述。具体而言，表的列存储在内存DBMS的RAM中的存储器页面中。存储器页面是存储器的地址空间中连续的可寻址的存储器单元。表的行为主的列存储在本文中被称为行页面的存储器页面中。根据本发明的实施例，表的行为主的列存储在被称为行页面分区的一组行页面中。

表的列为主的列存储在本文中被称为列页面的存储器页面中。每个列页面按列为主的格式存储列组的一个或多个列。对于表的列组，列组存储在被称为列分区的一组列页面中。表可以有多个列组，列组中的每一列存储在列分区中的一组列页面中。

图1绘出了根据本发明实施例的行页面分区和列页面分区。参照图1，它绘出了包括行为主的页面RP₁、行为主的页面RP₂和行页面RP_N的行页面分区RP，包括列页面DE₁的列分区DE，以及包括列页面F₁的列分区F。

在行页面分区中，每个行为主的页面将行的行为主的列按行为主的格式存储为行-部分元组。行的行-部分元组存储在行页面的行槽(rowslot)中。行和相应的行-部分元组及行槽被功能映射到行id，如将进一步详细描述的。

根据本发明的实施例，行页面在N个行槽中保持行的N个元组。每个行槽与行槽号关联，行槽号对应于行页面内的行槽的序号位置，并且被用来识别行页面内的行槽。行页面RP₁被分为槽1、2至N，每个槽按行为主的格式保持行为主的列A、B和C的行-部分元组。槽的槽号在图1中在列A中示出。同样，行分区RP₂和RP_N各自被分为行槽1、2至N，每个行槽按行为主的格式保持行为主的列A、B、C的行-部分元组。

行分区的行页面被顺序排序。行分区RP中行页面的行页面次序是行页面RP₁、行页面RP₂，然后是行页面RP_N，如由下标指定的。根据本发明的实施例，对应于行分区内行页面的次序的序数用作识别行页面的行页面id。行页面RP₁的行页面id是1，行页面RP₂的行页面id是2，行页面RP_N的行页面id是N，等等。

行的行id被功能映射到行分区中该行的位置。根据本发明的实施例，行id是基于行页面的行页面id和保持行的行-部分元组的行槽的行槽号利用数学公式得出的，如下。

(行页面Id-1)*N+行槽号

相应地，对于槽1、2和N，包含在行页面RP₁中的行的行id分别是1、2和N。对于行槽1、2和N，包含在行页面RP₂中的行的行id分别是N+1、N+2和2N。

列页面和分区

列分区DE存储包括列D和列E的列组的列。列分区DE包括列页面DE₁，以及其它未在图1中绘出的列页面。列分区中的列页面类似于行页面被顺序排序，其次序在标号的下标中表示。

存储在列页面中的列是在包括列槽的列行程(columnrun)中按列为主的格式。对于列分区的列组中的每一列，该列分区的每个列页面保持列行程。列页面DE₁包括分别存储用于列D和E的列值的列行程D和列行程E。

每个列行程具有相同数量的列槽。每个列槽与列槽号关联，列槽号对应于列行程内列槽的序号位置，并且被用来识别列行程内的列槽。列行程D包括列槽1、2至N²；列页面DE₁中的列行程E也包括槽1、2至N²。

列分区F包括列页面F₁和图1中未绘出的其它列页面。列页面F₁中的列行程F包括列槽1、2至N²。

对于表的给定行，存储在该行的列分区中的列值被存储在具有相同列页面id的列页面中和具有相同列槽号的列槽中。因此，在列页面DE₁的列行程D和列行程E，以及列页面F₁中的列F中，具有列号1的列槽保持同一行的列值。

根据本发明的实施例，列页面具有比相应行页面更大的存储器规格并且包含更大数目的槽。对于给定的列组，列页面存储对应的多个行页面的行的列值。列页面中槽的数目是行页面中N个槽的倍数。根据本发明的实施例，该倍数是N，但本发明并不限于此。因此，列分区DE和列分区F的每个列页面包含N²个列槽。

通过实际上基于行页面中行的位置的简单数学公式，列页面、其中的列槽、行页面和其中的行槽之间的上述布置促进行的行槽到保持该行的列值的列槽的功能映射。对于存储在行页面的行槽中的给定行，在表的每个列分区中，保持该行的列值的列页面的列页面id和列槽号是由下列公式CLR确定的。

CLR

列页面Id＝(行页面id–1)/N+1

列槽号＝((行页面id–1)*N+行槽号–1)％N²+1

例如，对于行N+2，行页面id是2并且其中的行槽号是2。根据上面的公式，保持行的列值的列分区DE的列页面id是(2–1)/N+1，这是1。列槽号是((2–1)*N+2–1)％N²+1，这等于N+2。除非另有规定，否则在本文给出的公式中的除法是整数除法，并且％指整数取模。

在上面的布置中并且根据公式CLR，行页面仅与一个列页面关联；行槽仅与一个列槽关联。但是，列页面与N个行页面关联，但列槽仅与一个行槽关联。关联是通过本文中所描述的公式CLR和其它公式规定的。通过使用简单的数学公式，以上一对一布置促进行槽和列槽的功能映射。实际上，保持行的列值的列槽和列页面由该行的表的行页面分区内该行的存储位置规定。

位置和行ID解析

位置解析是指确定行分区、行页面、列分区和/或列页面中行的位置的操作。列式位置解析是指：给定关于行页面和/或行分区中行的位置的输入(诸如行的行页面id和行槽号或行id)确定列分区和/或列页面列中行的位置。列式位置解析是基于公式CLR执行的。如上面所说明的，列式位置解析的结果是列页面ID和列槽号。

行位置解析是指：给定从其得出行的位置的输入(诸如行的列页面id和列槽号或者行id)确定行分区或行页面中行的位置。行位置解析的结果是行页面id和行槽号。可以通过使用公式来利用行槽和列槽之间的功能一对一映射，以快速执行行位置解析。下面的公式RLRC基于行的列页面id和列槽号产生行位置。

RLRC

行页面Id＝((列页面Id–1)*N²)+(列槽号–1)/N+1

行槽号＝(列槽号)％N

例如，为了列页面id是1的列槽号N+2确定对应的行页面，行页面被计算为((1-1)*N²)+(N+2–1)/N+1，这是2。为了确定对应的行槽号，行槽号被计算为(N+2)％N，这是2。

为了从行id确定行位置，可以使用下面的公式RLRR。

RLRR

行页面Id＝(行Id–1)/N+1

行槽号＝(行Id–1)％N+1

因此到目前为止利用所述公式CLR、RLRC和RLRR的行位置解析和列式位置解析产生逻辑位置；行页面id和行槽号包括行页面中行的逻辑位置，并且列页面和列槽号包括列页面中行的逻辑位置。为了访问存储器中的行，需要存储器地址。因此，位置解析还包括为行页面或列页面中的行生成存储器地址。

为了使得能够访问逻辑位置的存储器地址，页面目录在内存DBMS中被维护。页面目录将表的行页面id映射到行页面的存储器地址，并且将列组的列页面映射到列页面的存储器地址。为了利用行页面id和行槽号检索行的行-部分元组，页面目录被访问和检查，以确定映射到行页面的行页面id的存储器地址，并且行槽号被用作偏移量来访问行页面中的行元组。为了使用列页面和列槽号检索行的列值，页面目录被访问和检查，以确定映射到列页面的列页面id的存储器地址，并且列槽号被用作偏移量来访问列页面中的列值。

附加的页面结构

图2示出了与本文所述的各种数据库操作(诸如稍后讨论的列式扫描和就地更新操作)有关的具有附加细节的行页面和列页面。

参照图2，它绘出了行页面RP₁，其中列A作为主键列，列B作为存储行id的列。根据本发明的实施例，在列B中，行分区RP中的每个行-部分元组存储相应行的行id，从而允许对行的行id的快速解析。根据本发明的实施例，表可以包括在表的行为主的列中的主键。此外，表的行为主的列包括至少一个行控制列。行控制列R包括用于管理行的信息，包括用于并发和事务控制的信息，诸如引用计数、事务列表，等等。

根据本发明的实施例，列分区的每个列页面包括关于存储在列页面中的列值的值统计数据。列页面CP₁包括最小-最大统计数据MM和Bloom过滤器BM。最小-最大统计数据指定存储在列页面中的最小和最大列值。

Bloom过滤器是被用来识别不是集合的成员的值的概率数据结构。Bloom过滤器通过允许一定程度的误差来指示一大组值的存在。Bloom过滤器的性质使得Bloom过滤器对值的应用揭示出以下两种可能性之一：(1)值不在为其导出Bloom过滤器的集合中；或者(2)值可以但不一定在为其导出Bloom过滤器的集合中。即，Bloom过滤器的应用可能导致假阳性，但决不会导致假阴性。列页面的值统计数据中的Bloom过滤器被用来识别列值在列页面中的存在与否。它是从列页面的列值导出的。

内存DBMS可以存储、维护和使用其它结构用于优化数据访问。例如，行为主的列和列为主的列可以通过索引(诸如二进制树索引或位图索引)来加索引。这种索引可以由内存DBMS响应于接收到声明列的索引的DDL语句而为行为主或列为主的列创建和维护。

列式扫描

双重内存DBMS存储的能力是通过列式扫描的基本数据库操作的执行证明的。在列式扫描中，列被扫描，以确定具有满足一个或多个过滤标准的列值的行。为了说明的目的，这一个或多个过滤标准包括列值等于在由内存DBMS计算的查询的谓词中指定的谓词值的过滤标准。查询是由内存DBMS响应于接收到数据库语句而计算的。

列页面的列式扫描的输出包括识别具有满足一个或多个过滤标准的列值的行和/或指定每一行的位置的信息。根据本发明的实施例，输出包括一组行指针。行指针包括用于定位行的行-部分元组的位置信息。行指针可以包括行的行id，或者行的行页面id和行槽号。利用行的列式位置解析和行指针、或者行页面id和行槽号，行的列值可以在相应的行页面分区和列分区中定位。实际上，行指针识别所有行的列值的位置。

图3是绘出了双重内存DBMS存储的列式扫描过程的流程图。列式扫描过程处理列页面分区的每个列页面。

参照图3，对于每个列页面，在305，从列页面中的值统计数据确定存储在列页面中的任何列值是否能满足过滤标准。如果否，则避免对列页面的进一步列式扫描处理，并且没有行指针为该列页面返回。如果是，然后另一列页面由该过程进行处理。

在310，列页面中的列值被扫描。具有满足过滤标准的列值的列槽的列槽号被跟踪。

在315，从310中被跟踪的列槽号生成行指针。行指针是基于列页面的列页面id和被跟踪的列槽号利用行位置解析生成的。

在320，所生成的行指针被返回。然后，列分区的另一列页面由该过程进行处理。

就地更新

如前面所提到的，在双重内存列式存储下，行可以在存储列为主的数据的存储器中被就地更新。为了区别在双重内存列式存储下就地更新与用于更新列为主的数据的各种其它方法，在本文进一步详细地描述这各种其它方法。

如前面所提到的，在优先行拷贝的方法中，DBMS维护其数据库的两个版本，数据库的列为主的版本和数据库的行为主的版本。更新首先对行为主的版本进行，被提交或以其它方式完成，然后被应用到列为主的版本，这常常是按批进行的。

具体而言，在DBMS中执行的数据库事务更新行为主的版本。数据库事务最终被提交，由此提交由数据库事务在行为主的版本中进行的更新。在这些事务被提交之后，更新被应用和或以其它方式传播到列为主的版本。

在改变-内联方法中，当事务更新存储在列为主的格式的数据块中的行时，该行的列被缝合在一起，以便在数据块中存储该行的行为主的版本，数据块被相应地更新。当事务被提交时，数据块被提交，其中行以行为主的形式被存储。随后，数据块可以被重新格式化，以除去行的行为主的形式并且在数据块中将行恢复到列为主的形式。

在双重内存列式存储下的就地更新中，当数据库事务更新存储在行页面中的表的行和表的列分区时，改变在行为主的形式的行分区中和列为主的形式的列分区中进行。当数据库事务被提交时，行分区和列分区中的改变被提交。内存DBMS的数据库服务器没有为数据库事务生成并提交行的列为主的列的行为主的形式。

图4是绘出用于由DBMS的数据库服务器为了执行数据库事务(在本文中被称为“当前数据库事务”)而执行的就地更新的过程的流程图。数据库事务由内存DBMS响应于数据库服务器接收到请求更新的数据库语句而执行。为了说明的目的，“当前行”的列D由数据库事务利用新值更新。

参照图4，在405，行的行-部分元组被标记为删除。具体而言，行-部分元组的行控制列被标记为指示该行被当前数据库事务删除。该行的列值由数据库事务在行-部分元组中并在该行的对应列槽中保持不变。根据用于事务处理的协议，以这种方式标记列使得在当前数据库事务提交之前扫描该行的其它数据库事务能够看到处于在被更新之前存在的状态的该行。

在410，不被用来存储行的打开的行槽在表的行分区的行页面中找到。因为行槽是打开的，所以列组的对应列槽也是打开的。

在415，被更新的行存储在打开的行槽和对应的列槽中。列槽是基于行页面id和打开的行槽的行槽号利用列式位置解析识别和定位的。此外，新值存储在列D中。打开的行槽中的行控制列被更新，以反映行被存储在该行槽中，以便更新当前数据库事务的当前行。

在420，当前数据库事务被提交，由此提交打开的行槽和对应的列槽中的行。提交数据库事务可能需要更新相应列页面的统计数据，以反映现在在对应槽中提交的列值。列页面中的最小/最大统计数据和Bloom过滤器被更新，以反映加到列页面的列值的存在。

列的行程长度编码

列分区中的列可以利用行程长度编码进行压缩。行程长度编码是数据压缩的一种形式，其中相同数据值的序列被存储为数据值和计数的组合，而不是序列。计数表示由该组合表示的数据值的出现次数，并且在本文被称为行程计数；数据值在本文被称为行程值；组合在本文被称为编码行程。由编码行程表示的数据值的出现在本文被称为行程。行程长度编码对于具有相同数据值的较大出现序列的数据主体是特别有价值的。

根据本发明的实施例，存储在列分区中的单个列可以利用行程长度编码进行压缩。每个行程由列行程元组表示，这实际上是编码行程。列行程元组按列中出现的行程的相同相对次序存储在列槽中。

在L行存储在L个行槽中的表中列的行程长度编码中，列可以由存储在K个列槽中的K个列行程元组表示，其中K与L不同并且比L小得多。这种布置更改行槽与列槽之间的一对一映射关系，前面所述用于位置解析的公式基于这种映射关系。为了促进位置解析的执行，对行程长度编码列分区维护位置索引。位置索引也可以被用来给不是行程长度编码的列分区加索引。

除了行程长度编码，行分区或列分区还可以利用其它技术进行压缩，诸如字典压缩或增量编码。在本发明的实施例中，列分区可以利用字典压缩和行程长度编码进行压缩，由此编码字典记号(token)的行程。列的字典压缩在于2011年9月9日由TirthankarLahiri等人提交且标题为“ColumnDomainDictionaryCompression”的美国专利申请13/224,327中描述。

位置索引

根据本发明的实施例，位置索引被用来基于行位置信息(诸如行id或其它位置信息，诸如行页面id和行槽号)识别列值。位置索引是双向的，并且可以被用来确定与列值对应的行的行id、行页面id和行槽号的范围，并确定与列值对应的行的列页面id和列槽的列槽号。

图5绘出了根据本发明实施例的位置索引I，位置索引I给列分区P加索引。列分区P是利用行程长度编码进行压缩的。为了阐述的目的，列分区P的每个列页面包含两个“列行程元组”，每个“列行程元组”编码并表示列值的行程。列分区P依次包括列页面P₁、列页面P₂、列页面P₃和列页面P₄。列分区P₁包含列行程元组(V1,C1)，其中V1是行程值，C1是行程计数。列分区P中的其它列行程元组是完全相同的结构。列页面P₁中的下一个元组是(V2,C2)。在列页面P₁之后的是列页面P₂，具有列行程元组(V3,C3)，然后是(V4,C4)，等等。

位置索引I是包括节点I1、I2和I3的层次索引。位置索引I中的节点与位置索引I中的其它节点并且与列分区P中的列页面以父子层次结构组织。为了阐述的目的，每个节点包含两个“索引元组”，每个“索引元组”是其它索引节点的父亲，或者，在叶子索引节点的情况下，是加索引的列分区P中的列页面的父亲。

每个索引元组包含：(a)到孩子的链接，孩子是加索引的列分区的索引节点或列页面；和(b)聚合行程计数，这是实际上由索引元组的孩子表示的行程的行程计数的总和。行程的序列被称为聚合行程；聚合行程的行程计数的总和被称为聚合行程计数。因此，每个索引元组表示聚合行程并且包含聚合行程计数。

对于由索引节点表示的聚合行程，索引节点包括第一聚合行程、后续的第二聚合行程，等等。第一元组表示第一聚合行程并保持其聚合行程计数。下一个元组表示第二聚合行程并保持其聚合行程计数，等等。注意，列分区中的行程以及相应的位置是凭借索引节点中索引元组的次序以及索引节点之间的父子层次关系来表示的，其中层次关系反映了行程的次序。

上述位置索引的布置的含义是，实际上根索引节点表示加索引的列分区中的所有行程。参照图5，索引节点I3是根节点并包括两个元组。第一索引元组被链接到索引节点I1并包含作为C1、C2、C3和C4的总和的聚合行程计数。实际上，凭借其在索引节点I3中的次序及其覆盖第一行程的聚合计数的聚合计数，第一索引元组表示列分区P中(即，列页面P₁和P₂中)的第一行程。第二索引元组被链接到索引节点I2并包含作为C5、C6、C7和C8的总和的聚合行程计数。实际上，第二索引元组表示列分区P中(即，列页面P₃和P₄中)的第二和剩余行程。

索引节点I1是根索引节点I3中的第一元组的孩子并且表示第一元组的聚合行程。索引节点I1本身包含索引元组。第一索引元组被链接到列分区P₁并包含作为C1和C2的总和的聚合行程计数。这第一个索引元组凭借其在索引节点I1中的次序以及索引节点I1在位置索引I的父子层次结构中的位置来表示列分区P的第一行程(列页面P₁和P₂的那些行程)。第二索引元组凭借其在索引节点I1中的次序以及索引节点I1在位置索引I的父子层次结构中的位置来表示列分区P的接下来的行程(列页面P₃和P₄的那些行程)。

以与索引节点I1表示根索引节点I3中第一元组的聚合行程相同的方式，索引节点I2是根索引节点I3中第二索引元组的孩子并且表示第二元组的聚合行程(列页面P₃和P₄的那些行程)。

给定行的行id，位置索引I中的索引节点被遍历，以识别保持该行的列值的列行程元组和列页面id。重要的是，在具有行idR的行的列分区P中，在该行的编码行程之前的编码行程的总行程计数加上表示R的编码行程的行程计数必须至少和所述行id一样大。

在遍历期间，索引节点和索引节点元组被访问。当索引节点元组被访问时，累计行程计数被跟踪。如果累计行程计数加上被访问的索引元组的聚合行程计数覆盖所述行id，则孩子索引节点元组被访问。否则，索引元组的聚合行程计数被加到累计行程计数并且下一个索引元组被访问。最终，包含用于该行id的行程的列分区被访问并评估，以检索列值。

例如，假设行id是C1+C2+C3+C4+2并且C5大于2。在遍历位置索引I时，第一个被访问的节点是根索引节点I3。在检查其中的第一元组时，确定聚合行程计数C1+C2+C3+C4小于行id。因此，第一元组的聚合行程不能包括该行。接下来，第二元组被检查。由于累计行程计数C1+C2+C3+C4以及聚合行程计数C5+C6+C7+C8一起大于行id，因此索引节点I2必然表示覆盖该行id的聚合行程。第二索引元组链接到的子索引节点I2被遍历和访问。

接下来，索引节点I2中的第一元组被检查。由于累积的聚合行程计数C1+C2+C3+C4加上第一元组的聚合行程计数C5+C6至少与该行一样大，因此索引节点I3中的第一元组必然表示覆盖该行id的聚合行程。第一索引元组链接到的列页面P3被访问。基于累积聚合行程计数与行id之差(该差值小于C5)，确定第一列行程元组包含用于该行id的值(这是值V5)。

为找出行ID的逆遍历

在本发明的实施例中，索引节点的孩子具有到该索引节点的父链接。对于列页面，到父索引节点的父链接可以被存储在列页面中或页面目录中。位置索引I可以从下往上被遍历，以找出包含列值的行的行id和行id的范围。给出列值，具有匹配值的列行程元组被找出，并且位置索引I被遍历，以找出对应的行id或行id的范围。当每个节点被访问时，父索引元组的前一节点索引元组的聚合行程计数被累计，以确定用于列值的行id或行id的范围。

例如，对于列页面P4中的值V7，沿着列页面P4的父链接去访问节点I2。确定在列页面P4的父索引元组之前有索引元组；C5+C6，前一父索引元组的聚合行程计数，被累计。接下来，沿着用于索引节点I2的父链接去访问节点I3。确定在父索引元组之前有索引元组；C1+C2+C3+C4被添加到C5+C6的累计行程计数。位置索引I的遍历完成，找出行id的范围是(累计行程计数+1)至(C7-1)。

一旦对应的一个或多个行id被确定，行位置解析就可以被执行，以找出行页面分区和列页面分区中的行。

DBMS概述

本发明的实施例用在DBMS的上下文中。因此，对DBMS的描述是有用的。

DBMS管理数据库。DBMS可以包括一个或多个数据库服务器。数据库包括存储在存储器机构(诸如硬盘集合或者在内存DBMS的情况下为RAM)上的数据库数据和数据库字典。

用户通过向数据库服务器提交使数据库服务器对存储在数据库中的数据执行操作的命令来与DBMS的数据库服务器交互。用户可以是运行在客户端计算机上与数据库服务器交互的一个或多个应用。本文中多个用户也可以被统称为用户。

数据库命令可以是遵循数据库语言的数据库语句的形式。用于表示数据库命令的数据库语言是SQL。存在许多不同版本的SQL，有些版本是标准的，有些是专用的，并且存在各种扩展。DDL命令被发送到数据库服务器，以创建或配置数据库对象，诸如表、视图或者复杂数据类型。

基于盘的DBMS使用盘储存器来存储数据库。基于盘的DBMS是在数据项和相关的数据结构主要驻留在盘上的假设下设计、编程、配置并优化的。优化算法、缓冲池管理和加索引的检索技术是基于这个基本假设来设计的。

关于盘存储器的一个问题是，对数据项和数据结构的访问相当慢。即使当基于盘的DBMS已经被配置为在主存储器中高速缓存许多数据项和数据结构的时候，其性能也由于基于盘的数据驻留的假设而被束缚。这些假设不容易扭转，因为它们在处理逻辑、加索引方案和数据访问机制方面被硬编码。

内存DBMS主要在RAM中存储数据库。通过在RAM中管理数据库并优化用于RAM的数据结构和数据访问算法，甚至与完全高速缓存的、基于盘的DBMS相比，内存DBMS都能够提供改进的响应和吞吐量。例如，内存DBMS被设计为知道数据项在RAM中在存储器页面中驻留，并且因此能够采取到数据项的更直接路线，从而减少代码路径的长度，并简化算法和数据结构。

当盘驻留的假设被除去时，复杂性可以降低。机器指令数下降，缓冲池管理可以消失，不需要数据项和/或数据结构的额外拷贝，并且索引收缩。数据库语句可以被计算得更快。内存DBMS可以通过例如将数据从主存储器归档到盘或者通过维护基于盘或闪存的事务日志来提供数据库持久性。

双存储器DBMS可以将数据库的一部分存储为内存数据库并且将数据库的另一部分存储为基于盘的数据库。这种DBMS被配置为处理这两种类型的数据库存储的复杂性。内存数据库可以是基于盘的数据库的一部分的拷贝或镜像版本。作为替代，数据库的内存部分可以包括与基于盘的数据库中的数据库对象不同的数据库对象。双存储器DBMS的例子在由VineetMarwah、JesseKamp、AmitGanesh等人(甲骨文国际公司作为申请人)的、于2013年9月21日提交且标题为“Mirroring,inMemory,DataFromDiskToImproveQueryPerformance”的美国临时专利申请号61/880,852(案号50277-4464)中描述。

多节点DBMS由共享对同一数据库的访问的互连节点组成。通常，节点经网络互连并且以变化的程度共享对共享储存的访问，例如，对一组盘驱动器和其上存储的数据块的共享访问。多节点数据库系统中的节点可以是经网络互连的一组计算机(例如，工作站、个人计算机)的形式。作为替代，节点可以是网格的节点，其中网格由刀片服务器的形式的节点组成，这些节点与机架上的其它刀片服务器互连。

多节点数据库系统中的每个节点都托管数据库服务器。服务器(诸如数据库服务器)是集成的软件组件和计算资源的分配的组合，其中计算资源为诸如存储器、节点和用于在处理器上执行集成的软件组件的过程，软件和计算资源的组合专用于代表一个或多个客户端执行特定的功能。

数据库由数据库字典定义。数据库字典包含定义数据库中物理地或逻辑地包含的数据库对象的元数据。实际上，数据库字典定义数据库的全部。数据库对象包括表、列、数据类型、用户、用户权限和用于存储数据库对象数据的存储结构。数据库字典根据发出的DDL命令进行修改，以添加、修改或删除数据库对象。

例如，内存DBMS接收声明表和该表中的某些列的DDL语句。DDL语句可以声明列组、属于每个列组的列、以及列组是列为主的。通过不在DDL语句中明确地这么指定而缺省地，或者通过在DDL语句中明确地这么指定，可以将行为主的列声明为行为主。作为替代，如果DDL没有指定列是行为主还是列为主，则列可以缺省地是列为主。响应于接收到DDL语句，内存DBMS修改其数据库字典，以添加定义表、列组、作为以列为主的列组、属于该列组的列以及一个或多个行为主的列的元数据。进一步响应于接收到DDL语句，内存DBMS创建用于列组的列分区，以及用于行为主的列的一个或多个行分区。

数据库字典被DBMS参考，以确定如何执行提交到DBMS的数据库命令。

在DBMS中对数据库的改变是利用事务处理进行的。数据库事务是改变数据库数据的操作集合。在DBMS中，数据库事务是响应于请求改变的数据库语句(诸如作为更新请求插入行或删除行的数据操纵语言语句(DML))而被启动的。提交事务是指使事务的改变持久化。

依据事务处理，事务的所有改变都是原子地(atomically)进行的。当事务被提交时，或者所有的改变都被提交，或者事务被回滚。

硬件概述

根据本发明的一个实施例，本文所描述的技术由一个或多个专用计算设备实现。专用计算设备可以是硬连线的以执行所述技术，或者可以包括诸如被持久性地编程以执行所述技术的一个或多个专用集成电路(ASIC)或现场可编程门阵列(FPGA)的数字电子设备，或者可以包括编程为按照固件、存储器、其它储存器或者其组合中的程序指令执行所述技术的一个或多个通用硬件处理器。这种专用计算设备还可以联合定制的硬连线逻辑、ASIC或FPGA与定制的编程来实现所述技术。专用计算设备可以是台式计算机系统、便携式计算机系统、手持式设备、联网设备或者包含硬连线和/或程序逻辑来实现所述技术的任何其它设备。

例如，图6是说明本发明的实施例可以在其上实现的计算机系统600的框图。计算机系统600包括总线602或者用于传送信息的其它通信机构，以及与总线602耦合用于处理信息的硬件处理器604。硬件处理器604可以是例如通用微处理器。

计算机系统600还包括耦合到总线602用于存储信息和要由处理器604执行的指令的主存储器606，诸如随机存取存储器(RAM)或其它动态存储设备。主存储器606还可以用于在要由处理器604执行的指令的执行期间存储临时变量或其它中间信息。当存储在处理器604可访问的非暂时性存储介质中时，这种指令使计算机系统600变成为执行指令中所指定的操作而定制的专用机器。

计算机系统600还包括只读存储器(ROM)608或者耦合到总线602的其它静态存储设备，用于为处理器604存储静态信息和指令。提供了存储设备610，诸如磁盘、光盘或固态驱动器，并且存储设备610耦合到总线602，用于存储信息和指令。

计算机系统600可以经总线602耦合到显示器612(诸如阴极射线管(CRT))用于向计算机用户显示信息。输入设备614(包括字母数字和其它键)耦合到总线602，用于向处理器604传送信息和命令选择。另一种类型的用户输入设备是光标控制设备616，诸如鼠标、轨迹球或者光标方向键，用于向处理器604传送方向信息和命令选择并且用于控制显示器612上的光标移动。这种输入设备通常具有沿两个轴(第一个轴(例如，x)和第二个轴(例如，y))的两个自由度，以允许设备在平面内指定位置。

计算机系统600可以利用定制的硬连线逻辑、一个或多个ASIC或FPGA、固件和/或程序逻辑来实现本文所述的技术，这些与计算机系统相结合，使计算机系统600或者把计算机系统600编程为专用机器。根据本发明的一个实施例，本文的技术由计算机系统600响应于执行包含在主存储器606中的一条或多条指令的一个或多个序列的处理器604而执行。这种指令可以从另一存储介质(诸如存储设备610)读到主存储器606中。包含在主存储器606中的指令序列的执行使处理器604执行本文所述的处理步骤。在备选实施例中，硬连线电路可以代替软件指令或者与其结合使用。

如在本文所使用的，术语“存储介质”指存储使机器以特定方式操作的指令和/或数据的任何非暂时性介质。这种存储介质可以包括非易失性介质和/或易失性介质。非易失性介质包括例如光或磁盘，诸如存储设备610。易失性介质包括动态存储器，诸如主存储器606。存储介质的常见形式包括例如软盘、柔性盘、硬盘、固态驱动器、磁带，或者任何其它磁性数据存储介质，CD-ROM，任何其它光学数据存储介质，任何具有孔图案的物理介质，RAM、PROM和EPROM、FLASH-EPROM、NVRAM，任何其它存储器芯片或盒式磁带。

存储介质与传输介质截然不同但是可以与其结合使用。传输介质参与在存储介质之间传送信息。例如，传输介质包括同轴电缆、铜线和光纤，包括包含总线602的配线。传输介质还可以采取声或光波的形式，诸如在无线电波和红外线数据通信中产生的那些。

各种形式的介质可以参与把一条或多条指令的一个或多个序列携带到处理器604供执行。例如，指令最初可以在远程计算机的磁盘或固态驱动器上携带。远程计算机可以把指令加载到其动态存储器中并且利用调制解调器经电话线发送指令。位于计算机系统600本地的调制解调器可以在电话线上接收数据并且使用红外线发送器把数据转换成红外线信号。红外线检测器可以接收在红外线信号中携带的数据并且适当的电路可以把数据放在总线602上。总线602把数据携带到主存储器606，处理器604从该主存储器606检索并执行指令。由主存储器606接收的指令可以可选地在被处理器604执行之前或之后存储在存储设备610上。

计算机系统600还包括耦合到总线602的通信接口618。通信接口618提供耦合到网络链路620的双向数据通信，其中网络链路620连接到本地网络622。例如，通信接口618可以是综合业务数字网络(ISDN)卡、电缆调制解调器、卫星调制解调器，或者提供到对应类型的电话线的数据通信连接的调制解调器。作为另一个例子，通信接口618可以是提供到兼容的局域网(LAN)的数据通信连接的LAN卡。无线链路也可以实现。在任何此类实现中，通信接口618都发送和接收携带表示各种类型信息的数字数据流的电、电磁或光信号。

网络链路620通常通过一个或多个网络提供到其它数据设备的数据通信。例如。网络链路620可以通过本地网络622提供到主计算机624或者到由互联网服务提供商(ISP)626操作的数据设备的连接。ISP626又通过现在通常称为“互联网”628的全球分组数据通信网络提供数据通信服务。本地网络622和互联网628都使用携带数字数据流的电、电磁或光信号。通过各种网络的信号以及在网络链路620上并通过通信接口618的信号是传输介质的示例形式，其中所述信号把数字数据带到计算机系统600或者携带来自计算机系统600的数字数据。

计算机系统600可以通过网络、网络链路620和通信接口618发送消息和接收数据，包括程序代码。在互联网例子中，服务器630可以通过互联网628、ISP626、本地网络622和通信接口618发送应用程序的请求代码。

所接收的代码可以在其被接收时由处理器604执行，和/或存储在存储设备610或其它非易失性储存器中，供随后执行。

在前面的说明书中，已经参考众多的具体细节描述了本发明的实施例，这些细节可以随实现方式不同而不同。因此，说明书和附图应当相应地在说明性而不是限制性的意义上考虑。本发明范围的唯一且排他指示，以及申请人预期作为本发明范围的内容，是由本申请产生的权利要求集合的字面和等效范围，以这种权利要求产生的具体形式，包括任何后续的更正。