在关系数据库中组织数据记录的方法和设备

摘要

本发明的实施方式提供了用于在关系数据库中组织数据记录的方法和设备，其中该方法包括：为多个数据记录分别建立索引项，其中每个索引项包括计数器；对于受到随机访问的数据记录，更新相应索引项中的计数器的数值；以及基于多个计数器的数值，重组所述多个数据记录。利用本发明的实施方式的方法和设备，可以有效地提高加载数据记录的缓冲池的命中率而不影响对数据记录的顺序访问和插入操作的性能。

说明书

技术领域

本发明的各实施方式涉及数据记录的处理，并且更具体地涉及 在关系数据库中组织数据记录的方法、设备和相关计算机程序产品。

背景技术

当前已经开发了许多数据管理系统来对数据记录进行有效地访 问和组织。在这些数据管理系统中，关系数据库是企业级市场中占 主导地位的数据管理系统。随着访问的数据量的不断增加，对该关 系数据库的性能要求也变得越来越高。

以大型银行的银行卡业务为例，由于使用银行卡的客户众多， 每天关系数据库可能需要处理数以百万计的在线交易处理(简称 “OLTP”)，例如对账户信息的查询和更新。通过分析这些事务， 可以发现关系数据库的性能瓶颈通常在于将账户信息加载进存储器 (所谓的缓冲池)时的同步I/O操作。因此，如何有效提高缓冲池的 命中率以便改进访问数据的效率是克服这一性能瓶颈的关键。

另外，现有的数据组织策略是将数据记录以数据页为最小单位 进行组织。尽管随机数据访问通常仅需要读取或写入一个数据记录， 但关系数据库不得不将整个数据页加载进缓冲池。这样，可能许多 内存将被分配给不常被访问的数据记录，这无疑造成了缓冲池的浪 费，从而降低了缓冲池的命中率。

为了提高缓冲池的命中率，已经提出了如下的多种可能解决方 案，其中包括：

1)数据预取机制，该机制将所需的数据记录预先加载到缓冲池 中。然而，由于该数据预取机制要求数据库的优化器预先知道数据 访问的模式，而对于如上所述的账户信息查询和更新的数据访问情 形来说，由于下一次的数据访问行为(可以称之为随机数据访问) 很难预测，优化器无法预先准确知道数据访问的模式，因此改进此 类的随机数据访问性能仍是一个巨大的挑战。

2)增加缓冲池大小或优化缓冲池。通过增加加载数据记录的缓 冲池的大小，更多的数据记录可以被保存在内存中。但该解决方案 成本较高，此外也不太可能获得与数据表大小相同或接近的内存大 小。另外，还可以对缓冲池进行优化。例如，基于历史缓冲池命中 率趋势来自动地设置缓冲池大小(Heuristic automated method for ideal bufferpool tuning in a computer database，Scott R.Hayes，2001； System and Method to Improve processing time of Database by Cache Optimization，Hans-Juergen Bildhaeuser，2006)以及压缩缓冲池中的数 据记录以减小内存的使用量。然而，这样的优化解决方案并不直接 针对随机数据访问的属性-难以预测性。

3)改变数据结构。例如，一些应用从主表将经常使用与不经常 使用的数据记录归档到若干个表。然而，该解决方案需要对应用进 行显著的改变。同时，类似生成报告的批处理可能会变得复杂，因 为数据被分配到多个表，这将令应用逻辑难以控制。

4)以文件系统或操作系统中组织数据的方式来组织数据记录。 例如，频繁使用的数据应该存储在快速的存储设备中。然而，关系 数据库中的数据记录是按照聚集索引的顺序进行存储的，如文件系 统或操作系统的数据组织方式将影响数据库中数据记录的顺序访问 和插入操作性能。

发明内容

因而需要一种能够在关系数据库中高效地组织数据记录的方 法、设备和计算机程序产品，从而有效地提高缓冲池的命中率而不 影响对数据记录的顺序访问和插入操作的性能。

本发明的一个实施方式提供了一种用于在关系数据库中组织数 据记录的方法。该方法包括：为多个数据记录分别建立索引项，其 中每个索引项包括计数器；对于受到随机访问的数据记录，更新相 应索引项中的计数器的数值；以及基于多个计数器的数值，重组所 述多个数据记录。

本发明的另一实施方式提供了一种用于在关系数据库中组织数 据记录的设备。该设备包括：索引项建立装置，用于为多个数据记 录分别建立索引项，其中每个索引项包括计数器；索引项更新装置， 用于对于受到随机访问的数据记录，更新相应索引项中的计数器的 数值；以及重组装置，用于基于多个计数器的数值，重组所述多个 数据记录。

根据本发明的各实施方式，通过监视对数据记录的随机访问的 次数，并根据对随机访问次数的历史性数据的分析，将数据记录划 分在不同的物理分区，从而实现了数据记录的高效存储，有效地提 高了缓冲池的命中率，同时没有影响到数据记录的聚集属性。

附图说明

结合附图并参考以下详细说明，本发明各实施方式的特征、优 点及其他方面将变得更加明显，在附图中：

图1示意性示出了根据本发明一个实施方式的用于在关系数据 库中组织数据记录的方法的流程图；

图2示意性示出了根据本发明一个实施方式所形成的索引结构；

图3是示意性示出根据本发明一个实施方式的索引项中的计数 器更新的示图；

图4是示意性示出了根据本发明一个实施方式的基于索引项中 计数器的数值重组多个数据记录的示图；以及

图5示意性示出了根据本发明一个实施方式的用于在关系数据 库中组织数据记录的系统结构图。

具体实施方式

本发明的各实施方式提供了用于在关系数据库中组织数据记录 的方法、设备和计算机程序产品。在一个实施方式中，对用于随机 访问数据记录的索引项增加计数器，该计数器用于在对数据记录进 行随机访问时对该随机访问的行为进行计数。接着，基于该记录的 计数器的数值，重组多个数据记录。

在本发明的各实施方式中，数据记录表示存储在数据页中的结 构化数据项(如图3中示出的数据页中的每条账户信息，稍后将描 述到)，而随机访问行为表示在某段时间内对数据库的多次访问行 为(例如，查询、更新或删除等行为)之间没有太多的关联性，因 而数据库很难预测下次哪些数据记录将被访问到。这样的随机访问 行为不同于对数据库的顺序访问行为，顺序访问行为通常指多次访 问行为之间具有关联性，例如，按特定的顺序访问数据库的报表操 作，数据库可以根据该顺序预测哪些数据记录将在未来被访问到， 即而可以执行预取操作。

本发明的各实施方式利用各个数据记录受随机访问的历史次 数，将各个数据记录分配到不同的物理分区，例如将经常受随机访 问的数据记录存储在相同或连续的数据页，从而在被一起加载进缓 冲池时，有效地提高了缓冲池的命中率。同时，由于在分配到不同 的物理分区时，考虑了数据记录的聚集属性，从而不会对数据记录 的例如顺序访问和插入等操作的操作性能造成影响。

附图中的流程图和框图，图示了按照本发明各种实施方式的系 统、方法和计算机程序产品的可能实现的体系架构、功能和操作。 在这点上，流程图或框图中的每个方框可以代表一个模块、程序段、 或代码的一部分，所述模块、程序段、或代码的一部分包含一个或 多个用于实现规定的逻辑功能的可执行指令。也应当注意，在有些 作为替换的实现中，方框中所标注的功能也可以以不同于附图中所 标注的顺序发生。例如，两个接连地表示的方框实际上可以基本并 行地执行，它们有时也可以按相反的顺序执行，这依所涉及的功能 而定。也要注意的是，框图和/或流程图中的每个方框、以及框图和/ 或流程图中的方框的组合，可以用执行规定的功能或操作的专用的 基于硬件的系统来实现，或者可以用专用硬件与计算机指令的组合 来实现。

图1示意性示出了根据本发明一个实施方式的用于在关系数据 库中组织数据记录的方法100的流程图。如图1所示，方法100开 始于步骤S101。在步骤S102中，方法100为多个数据记录分别建 立索引项，其中每个索引项包括计数器。下面详细描述该步骤的具 体操作。

在本发明的各实施方式中，建立索引项可以认为是定义一种随 机访问行为。还以本说明书背景技术部分所描述的银行卡应用为例， 客户对账户信息(即，具体的数据记录)的访问可以通过针对“账号” 定义的索引来进行。例如，针对账户信息定义名称为 “ACCOUNT_INFO”的表，其创建形式示例性表达如下：

在该“ACCOUNT_INFO”上定义的聚集索引为 “IX_ACCOUNT_NO”，其创建形式示例性表达如下：

CREATE INDEX“IX_ACCOUNT_NO”on“ACCOUNT_INFO”(

AccountNo，

Name)；

如果将对数据记录的随机访问行为定义为根据“AccountNo”获 得一个数据记录，则查询语句可以示例性表达如下：

SELECT...FROM ACCOUNT_INFO WHERE AccountNo＝？

接着可以将对数据记录的随机访问行为建模为通过具有匹配列 (matching column，简称为“MATCHCOL”)的“IX_ACCOUNT_NO” 的相等匹配(equal matching)索引访问。例如，语句“RANDOM ACCESS WITH MATCHCOL＝1”可以用于指定该行为。当对数据记录 的访问行为与数目为1的MATCHCOL匹配时，则认为此次的对数 据记录的访问为一次随机数据访问。创建具有该语句的索引项可以 示例性地表达如下：

可以理解这里的预定限制条件语句“RANDOM ACCESS WITH MATCHCOL＝1”仅仅是示例性的，本领域技术人员可以根据需要预 先设定其他的限制条件语句。例如，可以将上面的MATCHCOL修 改为大于1，例如可以等于2。对于数目为2的MATCHCOL的情况， 如果对数据记录的访问行为匹配两列时(如按照前后顺序的 AccountNo和Name列时)，则将此次的对数据记录的访问行为视为 随机访问行为而非顺序数据访问。这样，就可以根据随机访问的预 定限制条件、在未设有计数器的索引项中增加计数器。增加了计数 器后的索引结构通过图2示意性示出(将在后文详述)。

在执行步骤S102后，方法100前进到步骤S103。在该步骤S103 中，方法100对于受到随机访问的数据记录，更新相应索引项中的 计数器的数值。下面示例性地描述步骤S103的具体操作。

当用户发起对数据记录的访问时，例如使用上面的包括 “WHERE AccountNo＝？”谓词的查询语句对数据记录进行查询时，关 系数据库中的优化器将选择出针对该访问行为的索引(即包括如上 建立的索引项的索引)，并且判断此次索引访问行为是否满足预先 定义的MATCHCOL的数目。如果此次索引访问行为满足预先定义 的MATCHCOL的数目，例如相等的MATCHCOL的数目大于或等 于1，则优化器认为此次对数据记录的访问是通过相等匹配索引访 问的一次随机数据访问，并且将建立的相应索引项中的计数器的数 值增1。图3(将在后文详述)示意性示出了当发生多次对数据记录 的随机访问后，多个数据记录的各自索引项中的计数器更新情况。

在执行步骤S103后，方法100前进到步骤S104，在该步骤S104 中，方法100基于多个计数器的数值，重组多个数据记录。后文将 结合图4来具体描述该重组多个数据记录的操作。

在重组多个数据记录后，方法100在步骤S105处结束。

图2示意性示出了根据本发明一个实施方式所形成的索引结构。 如图2中所示，该索引结构包括根页(或称为根节点页)、两个非 叶节点页以及四个索引项(存储在索引叶节点页中)。所示出的每 个索引项包括索引关键字(Index Key)、增加的计数器和行标识符 (RID)。正如本领域技术人员所知，关系数据库的索引项是由索引 关键字和RID构成的，其中索引关键字可以是如上所述的 “AccountNo”，而行标识符指示出数据记录的实际物理存储位置，其 并不表达在如前述的CREATE INDEX“IX_ACCOUNT_NO”语句中， 而通过增加如前所述的限制条件语句，本发明在这四个索引项中分 别增加计数器。尽管这里仅仅示出了两个非叶节点页和四个索引项， 但本领域技术人员可以理解实际的索引结构可以在数量和节点安排 上做出各种改变而不偏离本发明各实施方式的精神和范围。

图3是示意性示出根据本发明一个实施方式的索引项中的计数 器更新的示图。如图3中所示，在索引根节点下包括存储在索引叶 节点页中的八个索引项，每个索引项包括索引关键字、计数器和行 标识符，这里索引关键字示例性的设定为账号，而每个索引项指向 存储在数据页中的一个数据记录，该数据记录示例性地包括账号、 姓名、性别等。为了简化的目的，这里的示图省略了可能存在于索 引根节点和索引叶节点页之间的非叶节点页(如图2中所示出的)。 另外，这里的索引项、数据页以及数据页中的数据记录的数量也仅 仅是示例性的，实际的索引结构和数据记录可能要比这里示出的更 为复杂且数目更多。

从图3中可以看出，在索引关键字为“0000001”的索引项中， 记录随机访问次数的计数器的数值为99次，这表明在预定的时间间 隔内(例如一周或一个月)内，账号(即索引关键字)为“0000001”， 姓名为“John”的男性客户的数据记录已经受到99次随机访问，而 与账号为“0000001”的数据记录存储在同一数据页中的账号为 “0000002”，姓名为“Smith”的男性客户的数据记录已经受到5 次随机访问。

类似地，在账号为“0000003”的索引项中，计数器的数值为0， 这表明在与其他的索引项相同的预定时间间隔内，针对账号为 “0000003”、姓名为“Kate”的女性客户的数据记录并没有受到随 机访问，例如针对该账号的查询或更新操作，而与该姓名为“Kate” 的女性客户的数据记录存储在同一个数据页内的账号为“0000004”、 姓名为“Jay”的男性客户的数据记录则受到了55次的随机访问。

从图3中可以看出，由于将不受随机访问的账号为“0000003” 的数据记录和受频繁随机访问的账号为“0000004”的数据记录存储 在同一个数据页内。当对账号为“0000004”的数据记录进行随机访 问时，没有受到过随机访问的账号为“0000003”的数据记录也将被 加载到缓冲池中。当类似这样的情况在数量众多的数据页中发生时， 无疑会造成对缓冲池的巨大浪费，因此需要对存储的数据记录进行 重组。

图4示意性示出了根据本发明一个实施方式的基于索引项中计 数器的数值重组多个数据记录。不同于图3中的数据页，图4中的 多个数据页被划分为非频繁使用分区和频繁使用分区两类。受随机 访问次数较多的数据记录存储在频繁使用分区，而受随机访问次数 较少甚至是没有受到随机访问的数据记录则存储在非频繁使用分 区。例如，账号“0000001”、“0000004”...“0000008”的数据记录 在相同的预定时间间隔内分别受到“99”、“55”...“17”次的随 机访问，因此这些数据记录被重组到属于频繁使用分区的多个数据 页。类似地，由于账号“0000002”、“0000003”和“0000005”的 数据记录仅分别受到“5”、“0”和“0”次的随机访问，因此这些 数据记录被重组到非频繁使用分区的多个数据页。

尽管这里以预定的时间间隔为例来说明多个计数器的数值更 新，但本领域技术人员根据本发明的实施方式，可以想到定期或者 在计数器的数值达到预定阈值时，归档所述多个计数器的数值，以 便根据所述多个计数器的历史数值，重组所述多个数据记录。例如， 在到达预定的时间间隔后将多个计数器中的数值进行保存，并且在 执行了预定次数的保存后或者定期对各个计数器的数值进行求和， 从而可以得到关于各个计数器的历史数值。接着根据这些历史数值， 可以将数据记录重组到不同的物理分区。各个计数器的数值在每次 保存后被清零以便继续执行后续的计数操作。

另外，尽管在图4中将物理分区划分成频繁使用分区和非频繁 使用分区，但这样的划分仅仅是示例性的，本领域技术人员还可以 采用其他的划分方式。例如，可以将物理分区划分成三个部分，分 别为频繁使用分区、非频繁使用分区，以及处于频繁使用分区和非 频繁使用分区之间的中间分区，并且对于这三个分区分别设置针对 计数器的数值的不同阈值。例如，当某个数据记录受随机访问的次 数(或累加的次数)大于100次，则将该数据记录重组到频繁使用 分区，而当该数据记录受随机访问的次数在100和50次之间时，则 将该数据记录重组到中间分区，而当该数据记录受随机访问的次数 小于50次时，则将该数据记录重组到非频繁使用分区。

另外，根据本发明的一个实施方式，还可以针对多个分区来划 分比例，例如按照计数器的数值或多次累加后的数值(即历史数值) 对各个数据记录进行排列，然后将30％的受随机访问次数较多的数 据记录重组到频繁使用分区，将30％的受随机访问次数较少的数据 记录重组到非频繁使用分区，而将剩余的40％的受随机访问次数处 于中间区域的数据记录重组到中间分区。

除了上述的基于多个计数器的至少一个阈值以及多个计数器的 至少一个数值区间分配比例来重组数据记录以外，本发明的各实施 方式还可以使用合适的聚类算法来重组多个数据记录。例如K平均 算法，关于K平均算法的更多细节可参考J.A.Hartigan和M.A. Wong的“A K-Means Clustering Algorithm”，应用统计，第28卷第 1期第100-108页。

从图4中可以看出，存储在频繁使用分区和非频繁使用分区中 的数据记录依然保持了聚集索引的属性。例如，在所示的频繁使用 和非频繁使用分区中，各个数据记录依然按照账号的顺序存储在各 个数据页。因此，尽管根据本发明的各实施方式重组了各个数据记 录，但数据记录的聚集索引属性并不受到影响，从而也就不会影响 针对这些数据记录所执行的顺序访问操作和插入操作。

图5是示意性示出根据本发明一个实施方式的用于在关系数据 库中组织数据记录的系统500的结构图。如图5中所示，该系统500 包括应用501、关系数据库502、包括在该关系数据库502中的执行 计划503和优化器504、包括多个索引项的索引505、包括多个数据 记录的数据506、重组实用程序507以及访问趋势数据508。在一个 实施方式中，索引505是通过一个索引建立装置(未示出)预定建 立的。在另一个实施方式中，索引505是对先前建立的索引项进行 修改(例如，增加计数器)而形成的。下面将详细描述该系统500 的操作过程。

当应用501在步骤S509(例如如前所述的银行卡应用)发起对 关系数据库502的访问时，优化器504可以在运行时刻(bind time) 识别出此次数据访问是否是随机访问。如果此次数据访问是通过相 等匹配索引的访问并且该匹配列数与预先定义的列相等，如结合图1 示例性描述的MATCHCOL等于1，则优化器504认为此次的访问是 针对某个数据记录的一次随机访问，其将在步骤S510生成相应的一 个或多个执行计划503。该执行计划503不仅包括对数据记录访问的 操作，还包括对包括在索引项中的计数器的更新操作。在一个实施 方式中，执行计划503包括一个索引更新装置(未示出)，用于对于 受到随机访问的数据记录、更新相应索引505中索引项的计数器的数 值。

接着，当应用501调用关系数据库502在步骤S511运行执行计 划时，将对索引505中的相应索引项的计数器进行更新，即计数器 的值增1。由于本发明的各实施方式可以基于计数器的数值的长期历 史数据重组数据记录，因此不需要通过锁定操作来保证计数器的数 值完全准确。接着，在步骤S512处，关系数据库502可以通过索引 505中的相应索引项从包括多个数据记录的数据506获得所需要的 数据记录，并且在步骤S516返回给应用501。应用501在获得所要 求的数据记录后，向客户返回相应的结果集。

系统500中的重组实用程序507(例如，可以由一个重组装置来 实现)可以在步骤S513访问多个索引项中的计数器，从而可以定期 或在计数器的数值达到预定阈值时(如结合图1所描述的)获得各 个索引项中计数器的数值，并且在步骤S514中将多个计数器的数值 保存以形成访问趋势数据508。接着，重组实用程序507基于访问趋 势数据508中的各个计数器的数值，在步骤S515重组数据506中的 多个数据记录，例如如前所述按照预定的阈值或百分比来对多个数 据记录划分，从而被频繁随机访问的数据记录重组在相同或相近的 数据页，同时由于重组实用程序507是按照聚集索引的方式来重组 数据记录，因此不影响对重组后的数据记录的顺序数据访问和插入 操作。

尽管在这里为了简化附图的目的，以多个单向箭头示出了系统 500的操作，但本领域技术人员容易理解这里的单向箭头并不仅仅表 示来自单个实体的单方操作，其中也涉及多个实体之间双向交互的 操作，例如从数据506向关系数据库502返回数据记录等。

通过上面的详细描述，本领域技术人员可以理解本发明可以采 取完全硬件实施方式、完全软件实施方式或既包含硬件组件又包含 软件组件的实施方式的形式。在优选实施方式中，本发明实现为软 件，其包括但不限于固件、驻留软件、微代码等。

而且，本发明还可以采取可从计算机可用或计算机可读介质访 问的计算机程序产品的形式，这些介质提供程序代码以供计算机或 任何指令执行系统使用或与其结合使用。出于描述目的，计算机可 用或计算机可读机制可以是任何有形的装置，其可以包含、存储、 通信、传播或传输程序以由指令执行系统、装置或设备使用或与其 结合使用。

介质可以是电的、磁的、光的、电磁的、红外线的、或半导体 的系统(或装置或器件)或传播介质。计算机可读介质的例子包括 半导体或固态存储器、磁带、可移动计算机磁盘、随机访问存储器 (RAM)、只读存储器(ROM)、硬磁盘和光盘。目前光盘的例子 包括紧凑盘-只读存储器(CD-ROM)、压缩盘-读/写(CD-R/W)和 DVD。

适合与存储/或执行程序代码的数据处理系统将包括至少一个处 理器，其直接地或通过系统总线间接地耦合到存储器元件。存储器 元件可以包括在程序代码的实际执行期间所利用的本地存储器、大 容量存储器、以及提供至少一部分程序代码的临时存储以便减少执 行期间从大容量存储器必须取回代码的次数的高速缓冲存储器。

输入/输出或I/O设备(包括但不限于键盘、显示器、指点设备 等等)可以直接地或通过中间I/O控制器耦合到系统。

网络适配器也可以耦合到系统，以使得数据处理系统能够通过 中间的私有或公共网络而耦合到其他数据处理系统或远程打印机或 存储设备。调制解调器、线缆调制解调器以及以太网卡仅仅是当前 可用的网络适配器类型的几个例子。

从上述描述应当理解，在不脱离本发明真实精神的情况下，可 以对本发明各实施方式进行修改和变更。本说明书中的描述仅仅是 用于说明性的，而不应被认为是限制性的。本发明的范围仅受所附 权利要求书的限制。