Nothing Special   »   [go: up one dir, main page]

CN113688127B - 数据压缩技术 - Google Patents

数据压缩技术 Download PDF

Info

Publication number
CN113688127B
CN113688127B CN202110539890.3A CN202110539890A CN113688127B CN 113688127 B CN113688127 B CN 113688127B CN 202110539890 A CN202110539890 A CN 202110539890A CN 113688127 B CN113688127 B CN 113688127B
Authority
CN
China
Prior art keywords
data
columns
subset
subsets
column
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Active
Application number
CN202110539890.3A
Other languages
English (en)
Other versions
CN113688127A (zh
Inventor
J.史
R.舍卡特
J.斯米尔尼奥斯
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
SAP SE
Original Assignee
SAP SE
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by SAP SE filed Critical SAP SE
Publication of CN113688127A publication Critical patent/CN113688127A/zh
Application granted granted Critical
Publication of CN113688127B publication Critical patent/CN113688127B/zh
Active legal-status Critical Current
Anticipated expiration legal-status Critical

Links

Classifications

    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/28—Databases characterised by their database models, e.g. relational or object models
    • G06F16/284—Relational databases
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/221—Column-oriented storage; Management thereof
    • G—PHYSICS
    • G06—COMPUTING; CALCULATING OR COUNTING
    • G06F—ELECTRIC DIGITAL DATA PROCESSING
    • G06F16/00—Information retrieval; Database structures therefor; File system structures therefor
    • G06F16/20—Information retrieval; Database structures therefor; File system structures therefor of structured data, e.g. relational data
    • G06F16/22—Indexing; Data structures therefor; Storage structures
    • G06F16/2282—Tablespace storage structures; Management thereof
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/3084—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method
    • H03M7/3088—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction using adaptive string matching, e.g. the Lempel-Ziv method employing the use of a dictionary, e.g. LZ78
    • H—ELECTRICITY
    • H03—ELECTRONIC CIRCUITRY
    • H03M—CODING; DECODING; CODE CONVERSION IN GENERAL
    • H03M7/00—Conversion of a code where information is represented by a given sequence or number of digits to a code where the same, similar or subset of information is represented by a different sequence or number of digits
    • H03M7/30—Compression; Expansion; Suppression of unnecessary data, e.g. redundancy reduction
    • H03M7/46—Conversion to or from run-length codes, i.e. by representing the number of consecutive digits, or groups of digits, of the same kind by a code word and a digit indicative of that kind

Landscapes

  • Engineering & Computer Science (AREA)
  • Theoretical Computer Science (AREA)
  • Databases & Information Systems (AREA)
  • Data Mining & Analysis (AREA)
  • Physics & Mathematics (AREA)
  • General Engineering & Computer Science (AREA)
  • General Physics & Mathematics (AREA)
  • Software Systems (AREA)
  • Compression, Expansion, Code Conversion, And Decoders (AREA)

Abstract

描述了用于压缩数据和便于对压缩数据的访问的技术和解决方案。压缩可以应用于数据集的适当数据子集，诸如表的列。使用各种方法，适当数据子集可以被评估为包括在要使用第一压缩技术压缩的适当数据子集的组中，其中未被选择的适当数据子集不使用第一压缩技术来压缩。数据集中的数据可以基于适当数据子集的重新排序次序而被重新排序。当至少部分适当数据子集被压缩时，对数据集中的数据进行重新排序可以改进压缩。提供了便于访问以压缩格式存储的指定数据的数据结构。

Description

数据压缩技术
技术领域
本公开总体上涉及用于压缩数据的技术。特定的实现方式涉及用于提高压缩效率或用于更快速地从压缩数据源中检索选定数据的技术。
背景技术
软件应用，尤其是企业级软件应用，通常需要访问大量数据。存储这样的数据可能是有问题的，特别是如果期望以可由计算机快速处理的格式存储数据，诸如将数据存储在随机访问存储器(RAM)中。已经开发了各种压缩技术来存储数据，既可以将数据存储在主存储器(诸如RAM)中，也可以将数据存储在辅助存储器(诸如基于盘的技术)中。
作为特定的示例，通常期望OLAP数据库应用能够快速处理非常大的数据量。一些数据库系统(诸如位于德国沃道夫的SAP SE的SAP HANA)使用存储器内(in-memory)列存储技术。在列存储数据库中，数据以列格式在存储器中维护，其中每列包含该列的多行数据，与之相对的，在行存储数据库中逐行存储数据，在行存储数据库中，每行存储多列的数据。列存储数据库可能是有用的，包括因为列存储数据库可以利用压缩技术，诸如字典压缩和游程(run-length)编码。然而，由于大数据量以及涉及压缩数据的其他问题，诸如能够快速地定位特定数据值，改进的压缩技术以及用于管理和访问压缩数据的技术仍然具有重大意义。
发明内容
提供本概述是为了以简化的形式介绍一些概念，将在下面的详细描述中进一步描述这些概念。本概述不旨在标识所要求保护的主题的关键特征或必要特征，也不旨在用于限制所要求保护的主题的范围。
描述了用于压缩数据和便于访问压缩数据的技术和解决方案。压缩可以被应用于数据集的适当数据子集，诸如表的列。使用各种方法，适当数据子集可以被评估为包括在要使用第一压缩技术压缩的一组适当数据子集中，其中未被选择的适当数据子集不使用第一压缩技术压缩。可以基于针对适当数据子集的重新排序次序(sequence)来对数据集中的数据进行重新排序。当至少部分适当数据子集被压缩时，对数据集中的数据进行重新排序可以改善压缩。提供了便于访问以压缩格式存储的指定数据的数据结构。
在一个方面，提供了一种用于确定要压缩的多个适当数据子集的适当数据子集的方法。特定的实现方式可以包括确定应该使用游程编码压缩的表的列和应该保持未压缩的列。
接收包括第一多个适当数据子集的数据集。在特定的示例中，数据集是表，并且第一多个适当数据子集对应于表的列。每个适当数据子集包括数据集的多个元素，其中，元素与给定适当数据子集中的相应位置相关联。例如，适当数据子集可以包括表的多个行的值。可以对表的列中的数据元素进行排序，使得可以通过从列的相同位置处的列中检索值来重构表的行。
确定第一多个适当数据子集的基数(cardinality)。基数是指适当数据子集中唯一值的数量，诸如给定列中唯一值的数量。第一多个适当数据子集通过对基数进行升序来重新排序。对于第一多个适当数据子集的第二多个适当数据子集的相应适当数据子集，确定第一尺寸。对于第二多个适当数据子集的相应适当数据子集，使用第一压缩技术压缩适当数据子集，以提供压缩后的适当数据子集。
对于第二多个适当数据子集的相应压缩后的适当数据子集，确定第二尺寸。对于具有小于第一尺寸的第二尺寸的第二多个适当数据子集的相应适当数据子集，将相应适当数据子集添加到要使用第一压缩技术压缩的一组适当数据子集中。
在另一个方面，提供了一种用于确定在压缩数据集的适当数据子集时使用的顺序(order)的方法。在特定的示例中，该方法可以表示确定表列的顺序，其中，该顺序用于在对表列的至少部分进行压缩之前对表的行进行重新排序。
接收第一多个适当数据子集。适当数据子集具有第一顺序，并且包括多个数据元素。数据元素与适当数据子集中的位置相关联，并且给定适当数据子集中特定位置处的数据元素与其他适当数据子集中给定位置处的其他适当数据子集中的数据元素相关。例如，适当数据子集可以包括表的多个行的值。可以对表的列中的数据元素进行排序，使得可以通过从列的相同行位置处的列中检索值来重构表的行。
如下确定适当数据子集的第二顺序。确定第一多个适当数据子集的第一适当数据子集和第一多个适当数据子集的第二适当数据子集之间的相关值。将相关值与阈值进行比较。确定相关值满足阈值。基于确定相关值满足阈值，将第二适当数据子集添加到包括第一适当数据子集的组中。
使用第二顺序对第一多个适当数据子集的数据元素进行重新排序。压缩第一多个适当数据子集的至少部分的数据元素。
在另一个方面，提供了一种用于检索包括多个数据元素的数据集的指定数据元素的值的方法。在特定的示例中，该方法可以用于检索使用字典压缩压缩的压缩后的表列的指定行的值ID。
接收对包括多个数据元素的数据集的第一数据元素值的请求。确定具有多个数据元素位置的第一位置组，第一位置组包括第一数据元素值。确定为第一位置组指定的第一逻辑指针值。解除第一逻辑指针到包括数据元素位置和数据值的第一数据结构的引用。识别第一数据元素在第一数据结构中的位置。确定在第一数据结构中为第一数据元素指定的第一值。响应于该请求，返回第一数据元素值。
本公开还包括被配置为执行上述方法或包括用于执行上述方法的指令的计算系统和有形的非暂时性计算机可读存储介质。如本文所述，各种其他特征和优点可以根据需要结合到这些技术中。
附图说明
图1是示出字典压缩技术的图。
图2是示出对于表的一个或多个列、如何基于对行的重新排序来对表进行重新排序的图。
图3是示出用于存储游程压缩信息的不同技术、以及如何通过仅对表的特定列进行压缩来实现改进的压缩的图。
图4是示出在描述某些公开技术中使用的记号(notation)的表。
图5是选择要压缩的表列的“第一局部最小”方法的实施例的伪代码。
图6是选择要压缩的表列的“最佳局部最小”方法的实施例的伪代码。
图7是图6的方法的变体的伪代码，其中放弃了对列进行扩展。
图8是示出改变用于对表进行重新排序的列次序如何能够提供不同压缩级别的图。
图9是可以用于对要压缩的表列进行排序的“相关束(correlation bundle)”技术的实施例的伪代码。
图10是示出可以表中的列之间的相关性如何确定并用于形成(诸如在图9的技术中的)相关束的图。
图11是图9的技术的变体的伪代码，其中可以基于相关束中的列之间的基数差来细分相关束。
图12是图11的技术的变体的伪代码，其中通过对压缩尺寸进行升序来对相关束内的列进行排序。
图13是示出可以用于便利检索经游程存储(run-store)编码的游程压缩数据中的特定值的数据结构的图。
图14是用于描述用于计算压缩后的表的尺寸的技术的表。
图15是示出用于压缩以列存储格式维护的表中的至少部分数据的过程的图。
图16是当被压缩的列集中包括额外的列时，使用位置存储游程压缩或游程存储游程压缩的各种数据集的压缩结果的曲线图。
图17是当被压缩的列集中包括额外的列时，游程存储游程编码和位置存储游程编码的压缩结果的比率的曲线图。
图18是示出当额外的列被添加到压缩后的表列集时，表数据的总尺寸、表的压缩列的尺寸和表的未压缩列的尺寸的曲线图。
图19是示出用于选择要压缩的列的各种选择技术的结果的表。
图20是示出用于确定在表压缩之前对表的行进行重新排序时使用的列顺序的各种排序技术的结果的表。
图21是可以实现所公开的技术的示例数据库环境的框图。
图22是用于确定要压缩的数据集的适当数据子集的示例方法的流程图。
图23是用于确定数据集的适当数据子集的压缩顺序的示例方法的流程图。
图24是使用逻辑指针在包括压缩数据的数据结构中定位位置组起始点的示例方法的流程图。
图25是可以实现一些所描述的实施例的示例计算系统的图。
图26是可以结合本文所描述的技术使用的示例云计算环境。
具体实施方式
示例1–概述
软件应用，尤其是企业级软件应用，通常需要访问大量数据。存储这样的数据可能是有问题的，特别是如果期望以可由计算机快速处理的格式存储数据，诸如将数据存储在RAM中。已经开发了各种压缩技术来存储数据，既可以将数据存储在主存储器(诸如RAM)中，也可以将数据存储在辅助存储器(诸如基于盘的技术)中。
作为特定的示例，通常期望OLAP数据库应用能够快速处理非常大的数据量。一些数据库系统(诸如位于德国沃道夫的SAP SE的SAP HANA)使用存储器内列存储技术。在列存储数据库中，数据以列格式被维护在存储器中，其中每列包含该列的多行数据，与之相对，在行存储数据库中逐行存储数据，其中，每行存储多列的数据。列存储数据库可能是有用的，因为列存储数据库可以利用压缩技术，诸如字典压缩和游程编码。然而，由于大数据量以及涉及压缩数据的其他问题，诸如能够快速地定位特定数据值，改进的压缩技术以及用于管理和访问压缩数据的技术仍然具有重大意义。
在一个方面，本公开提供了可以用于选择要压缩的表的列的技术。也就是说，在至少一些情况下，可以通过留下表的某些列不被压缩来实现更高的压缩级别。
在另一个方面，本公开提供了可以用于确定列应该被排序(sort)的次序的技术，其中根据以所确定的排序次序对列进行排序而产生的重新排序来对表的行进行排序。在一些情况下，确定排序的顺序可以改善压缩结果。例如，排序可以使得表整体上具有更少的较长长度的值游程(run)，这可以使用游程编码来提供改进的压缩结果。
压缩数据有时可以以不同的格式存储。在游程编码的情况下，信息可以被存储为游程存储或位置存储。通常，游程存储提供更好的压缩，但位置存储便利从压缩数据中检索选定的值。本公开提供了一种可以用于加快对以游程存储格式存储的数据的访问的数据结构。
所公开的技术可以一起使用，也可以单独使用。此外，所公开的技术可以与其他技术一起使用。例如，要使用游程编码压缩的数据可以可选地首先使用字典压缩来压缩。
示例2–示例字典压缩技术
图1示出了如何使用字典压缩来压缩一系列数据值，诸如关系数据库系统的表的数据列的数据值。图1示出了未压缩的表110，其具有表示科目(诸如大学或学院环境中的课程的科目)的列(或字段或属性)114，以及表示在课程中可能已经获得的成绩的列118。
列114、118包括分别被示为值122a-122c的多个离散值122和被示为值126a-126d的离散值126。注意，表110的行130中的一些具有相同的值。也就是说，给定的列114、118可以具有多次出现的值122、126。列中唯一值的数量可以称为列的基数。因此，列114的基数为3，因为它有三个唯一值(CS，数学，物理)，而列118的基数为4(具有值A、B、C、D)。一般地，列的基数可以具有从1(即所有值都相同)到等于表中的行(或记录)的数量的基数(即所有值都不同，诸如如果列充当表的主键(primary key))的范围。
字典压缩为列中的每个唯一值分配值ID。可以通过用值ID代替值来压缩列。可以看出用整数代替二十个字符的串是如何节省存储空间的。表134是列114的示例字典，表138是列118的示例字典。每个字典134、138具有值ID的列142和提供与该值ID相关联的原始字段值的列146。注意，每个值ID和值都是唯一的，使得值ID列142的基数和字段值列146的基数都等于各自字典134、138中的行数。
表150表示应用了字典压缩后的表110。列154和158对应于列114、118，但是原始字段值已经被由相应字典130、134所指示的值ID所代替。例如，表110的行130a对应于表150的行162a。列154的行162a的值不是“物理”，而是“0”，“0”是在列114的字典134中为“物理”所指定的值ID。列158的行162的值具有为“0”的值，该值是在列118的字典138中为“A”所指定的值ID。
注意，表150的行162与表110的行130的顺序相同。如下所述，在一些情况下，通过对表的列进行重新排序可以实现更好的压缩。在这样的情况下，表中的其他列以类似的方式被重新排序，使得所有的值在每个列中都处于相同的位置，即使这些列可以(例如，以向量或数组)被分开存储，并且即使一些列可以被压缩而其他列可以不被压缩。在重新排序后的表中中维护原始表的特定行的信息可能很重要，因为这可以允许通过在每个重新排序后的列的相同的、相应的位置选择值来重构原始表的整个行。但是，在其他情况下，不需要跨列保留行次序，诸如当要逐列计算聚合值时，并且对检索同一行中的多个列的值不太感兴趣。
示例3–示例基于列排序顺序的行重新排序
如示例2所述，可以对列进行排序。当列是具有多个列的表的部分时，通常先选择一个列进行排序，然后将该重新排序的结果应用于表中的其他列。图2示出了如何对与图1的经字典编码的表150相对应的表210进行排序。
表210具有列214、218和行222。每个行222可以表示特定的实体(即，由表210表示的实体类型的实例)，使得对于一行的列214、218中的值226具有某种关系(例如，特定课程的特定成绩，如图1的表110所示)。在至少一些情况下，可能期望检索给定行的多个列214、218的值226。
在这个简单示例中，由于表210具有两个列214、218，因此存在用于对列进行重新排序的两种可能的选项—(1)对列214中的值进行排序，然后将得到的顺序应用于列218；或者(2)对列218中的值进行排序，然后将得到的顺序应用于列214。
表230示出了列214a，其具有与列214中的值相对应的值226，但是现在这些值已经被重新排序，使得值ID的值从表中的第一个记录234a到表中的最后一个记录234b是升序的。与表200的列218相比，列218a已经被重新排序。对列218a的重新排序是通过将列214a的顺序应用于列218中的值来实现的，使得给定行222中的值被保留在表230的行234中，即使该行可能出现在表230中与表210中不同的位置处。例如，可以看出，表210的第二行222a是表230的第五行234c。还可以看出，尽管列214a的值226是有序的，但是列218a的值是无序的(至少不按值排序，而是基于列214a的排序、按行222来排序)。
表240示出了与列214、218相对应的列214b和218b，但是行244(以及列214b、218b的相应的值226)是按列218的值排序的(与表230相比，是按列214的值重新排序的)。可以看出，列218b的值226是升序排列的，并且列214b的值已经被重新排序以保留表210的行222。继续上面的示例，行222a(即表210的第二行)出现在表240的行244a(即第四行)。
如将在后续示例中讨论的以及在示例1中描述的，对表的列进行重新排序可能是有益的，因为这样可以使用诸如游程编码的技术来改进列压缩。本公开描述了用于确定表的列的顺序的策略，该表的列的顺序应该用作对表的行进行重新排序的基础。这些策略可以用于未被压缩的表，或者也可以用于已经(或将)以另一种方式(诸如使用字典压缩)压缩的表。
示例4-用于存储游程压缩信息的示例技术
图3示出了如何使用游程编码来压缩数据(诸如关系数据库系统中的表的列中的值)。图3示出了表310，其对应于图2的表230，但是被旋转，使得表230的列214a、218a已经被旋转，使得列214a、218a形成表310的行314。旋转是为了便于表示，但也示出了如何将压缩技术应用于数据集，即使数据集不是作为列维护的、或者与表的列不相对应。
游程编码考虑了数据序列中的重复值，其中数据结构可以跟踪值以及在遇到不同值之前该值重复的次数。表330示出了对表310应用游程编码的结果。表330的行334a为“科目”(旋转后的)列314a提供值ID 338。对于每个值ID 338，行334b存储特定值ID 338的游程342。以类似的方式，行346a、346b存储表310的“成绩”列314b的值ID 350和游程354。因此，表330的每个列358为值ID 338的出现提供值ID 338和游程342的组合。
作为如何构建表330的示例，考虑表310的行314a。行314a从为“0”的值ID开始，并且该值在接下来的两个位置重复——值ID“0”连续出现三次。该信息通过在单元350a中提供为“0”的值ID，并在单元350b中提供为“3”的游程而被记录在表330中。因此，表330中的一个列(和两个值)可以存储表310中三个列的数据(六个值)，从而进一步压缩表310中已经使用字典压缩进行了压缩的数据。
表330表示存储游程编码信息的一种方式，其可以被称为游程存储游程编码，因为表330存储游程。表360表示代表该信息的一种替代方式，其可以被称为位置存储游程编码。表360包括存储值ID的行364a、364b和存储值的原始序列中相应的值ID(例如，表310的给定列372中)出现的位置的行368a、368b。然而，当值序列中值ID发生改变时，表360仅包括一对行364、368(对应于被定向为行314a、314b的列)的条目(即，新的列376)。
例如，表310的行314a从位置0的值ID“0”开始，因此该信息被输入到表360的行364a、364b的第一位置。为“0”的值重复，直到行314a的位置3，在该位置3处，出现为“1”的值。因此，为“1”的值ID和为“3”的位置被输入到行364、36b的第二位置。假设表的行364、368的集合中的一对给定的相邻列之间的所有位置都具有该对中最左边的列的值ID。继续此示例，因为“1”直到位置“3”才出现，所以表360指示对于在行364中的第一位置(位置0)开始并且在行314a中为“1”的值的位置(位置3)之前的最后一个位置结束的所有位置都存在为“0”的值ID——在这种情况下，行364的值指示位置0-2具有为“0”值ID。
测量压缩方案的效率可能是有用的。可以用于确定压缩效率的一种测量是确定表示表(或表分量，诸如特定的列)所需的比特数。表310的行314a的值350a和行314b的值350b每个都需要两比特来存储(因为值在0-3之间，所以可以被表示为00、01、10、11)。由于每行314a、314b具有十个位置，存储单个列的比特数是10*2＝20比特，因此存储整个表的成本是20比特/列*2列＝40比特。
在一些情况下，对列或表进行压缩可能更高效，但在其他情况下，对表中的一个或多个列(包括所有列)进行压缩可能比压缩后的对应列使用更多的空间，因为必须为值本身和游程存储值。随着游程越来越长，并且游程越来越少(例如，连续重复值越来越多)，相比于对数据的未经压缩的表示，游程编码通常提供更高效的存储。
在表330中，行334a和行334b两者都已经使用游程编码进行了压缩。行334a包括0和2之间的值，因此该信息需要两比特。行334a包括三个位置，因此需要2*3＝6比特来存储行334a中的数据。行334b具有值3或4，因此需要三比特来编码该信息。因为行334b也具有三个位置，所以需要3*3＝9比特来存储行334b中的数据。因此，总体而言，与行314a相对应的数据需要15比特来存储。转到行314b，表330中的相应数据在行346a、346b中。行346a具有八个位置，并且需要两比特来表示可能的值(0-3之间)，总共8*2＝16比特。类似地，行3346b具有八个位置并且需要两比特来存储可能的值(在0和3之间)，总共为8*2＝16比特。因此，需要32比特来存储与行314b相对应的数据。因此，表330需要15+32＝47比特来存储，这比存储未压缩的表310所需的40比特多。
如将进一步描述的，本公开提供了允许对表中少于所有数据的压缩的技术，诸如通过对表中少于所有的列进行压缩。对于使用压缩将节省空间的列，可以使用压缩；并且对于压缩会占用更多空间的列，可以省略压缩。
表380示出了与表310的行314a相对应的、但是已经如对于表330的行334a所述被压缩的行384a、384b。从前面的示例可知，行384需要15比特来存储。行314b保持未被压缩。为了存储行314b中的数据，需要两比特来存储值ID(具有0-3之间的值)，并且行314b具有十个位置。因此，行314b需要10*2＝20比特来存储。总的来说，表380需要15+20＝35比特来存储，比存储未经压缩的表310高效5比特，比压缩所有数据高效12比特，如表330所示的。
示例5-用于选择要压缩的表列的示例技术
如示例4中所解释的，在具有多个数据子集的数据集合(诸如具有多个列的表)中，压缩数据集合的所有子集实际上可能需要比原始的未压缩数据更多的存储空间(其中未压缩的数据是指在特定压缩技术(诸如游程编码)之前的数据，即使这些数据可能已经使用另一种技术(诸如字典压缩)压缩过)。本公开提供了用于确定集合中的哪些数据子集应该被压缩以及哪些子集(如果有的话)应该留下而不被压缩的技术。
尽管描述了对单个压缩技术的评估，但是所公开的技术可以用于评估使用不同的压缩技术的压缩。例如，如果使用游程编码未能有效压缩数据列，则该数据列可以保持不被压缩、或者该数据列可以针对另一种类型的压缩(诸如字典压缩，如果该列尚未使用字典压缩被压缩过)而被评估。可以针对不同的压缩技术(诸如只要能提供一定存储效率就受到青睐的一种技术、以及如果该受到青睐的技术不降低存储要求则被评估的其他技术)设置优先级或顺序。或者，可以针对给定的数据集评估多种类型的压缩，并且可以使用提供最高压缩级别的压缩技术。然后，对于整个数据集，一些技术针对数据集的所有子集可以不使用压缩或使用单个压缩技术，而其他技术针对数据子集不使用压缩或使用多种不同压缩技术中的一种(例如，一个列可以是未被压缩的，另一个列可以使用游程编码来压缩，而另一个列可以使用除了游程编码之外的技术来压缩)。
为了便于呈现，此示例5和本公开的其他部分涉及为了压缩而评估表的多个列。然而，这些技术可以被应用于其他数据集合/数据子集，只要该讨论没有另外明确地仅适用于列数据。在一些情况下，这些技术可以被应用于数据集的适当数据子集，其中适当数据子集包含的元素少于数据集中的所有元素。在更具体的情况下，每个适当数据子集是数据集的唯一适当数据子集(例如，任何两个适当数据子集的交集是空集)。在更具体的示例中，在数据集的所有适当数据子集中，元素的数量是相等的。可以对适当数据子集中的数据元素进行排序，使得在任何给定适当数据子集中特定位置处的适当数据子集中的数据元素之间存在关系。
此示例5以以列格式存储的表T为例(即，该表的数据被保持为连续的列值，而不是存储该表的各个行的多个列的连续值)。表T具有列总数nc和行总数nr。要压缩(诸如使用游程编码)的列的数量被指定为p。选择进行压缩的列可以被称为主(primary)列，并且包含在主列集Pset中。因此，未选列或“次(secondary)”列的数量为p-nc。除非另有说明，此示例5以及本公开的其他示例可以使用图4的表400中所示的记号。
为了确定要包含在Pset中的列，通常表T中的列可以按基数被重新排序，基数最低的列(预期将从压缩技术(诸如游程编码)中受益最大)在左边，并且基数较高的列在右边。至少在这一点上，列的原始行对应关系被保留，因此通过对列进行重新排序不会丢失任何信息。
列可以被递增地分析，以确定它们是否应该被添加到主列集Pset中。表中nc个列的集合意味着存在个列的子集(即，nc个列的幂集具有为的大小)。至少一些公开的技术使用考虑个可能的子集中至多nc个子集的增量选择(incremental selection)技术。
图5提供了在对表中的列进行压缩时获得的第一局部最小处停止的增量选择技术的伪代码500。按基数对列进行排序后，列被压缩。压缩后尺寸减小的每个列(或在一些情况下具有相等的尺寸或减小的尺寸)被添加到主列集Pset中。一旦遇到不能受益于压缩的列(例如，需要与未被压缩的列相同或更多的空间来存储)，该算法可以停止。也就是说，可以预期，基数比被评估为不能受益于压缩的列高的列也不能受益于压缩。实际上，第二列是否受益于压缩可能与第二列的基数是否高于(或等于)第一列没有直接关系。例如，即使第二列比第一列具有更高的基数，第二列也可能比第一列具有更少/更长的游程，因此即使第一列不受益于压缩，第二列也可以受益于压缩。本公开提供了用于处理该场景的技术。
根据伪代码500的“第一局部最小”增量选择技术，Pset中的主列被压缩，而次列保持未被压缩。示例4中的讨论展示了这种情况的好处，其中具有未压缩列314b的表380相比于具有被压缩的两个列314a、314b的表330，需要更少的存储空间。
图6提供了另一种增量选择技术的伪代码600，其可以被称为“最佳局部最小”选择技术。伪代码600中描述的技术类似于伪代码500，因为列首先按基数升序被排序。然后压缩所有列。在每个列位置，基于压缩该列位置和所有先前的列位置来确定表的压缩尺寸。压缩列的尺寸被添加到未压缩列的尺寸中。换句话说，对于具有列...的表，表在列i处的压缩尺寸是列...i的压缩值和列i+1...nc的未压缩值。因此，该技术为nc个列中的每个列产生压缩尺寸。nc个列中为整个表产生最低整体压缩尺寸的最后一列被选为Pset中的最后一列。
例如，假设表具有五个列，并且表的压缩值总体上是25、20、28、18、30。因为18是该表的最低压缩尺寸，所以列0-3将包括在Pset中并被压缩，而列4将保持未被压缩。如果改为使用第一局部最小技术，列0、1将正是包括在Pset中的列，并且整体压缩将劣于使用最佳局部最小技术的结果。
相比于“第一局部最小”技术，“最佳局部最小”技术执行起来更耗时，因为所有列都是以“最佳局部最小”技术压缩的，并且计算了具有多个列排列(permutation)的表的压缩尺寸，而不是一旦识别出任何不受益于压缩的列就停止。然而，“最佳局部最小”技术可以导致更高的整体压缩，因为它可以识别没有使用“第一局部最小”技术评估的Pset的列。
图7提供了另一种增量选择技术的伪代码700，其可以被称为“放弃对列进行扩展的最佳局部最小”选择技术。伪代码700中描述的技术类似于伪代码500、600，因为列首先按基数升序被排序。然后压缩所有列。如果一个列受益于压缩，它将被添加到主列集Pset中。与“第一局部最小”技术相比，“放弃对列进行扩展的最佳局部最小”技术执行起来更耗时，因为所有列都是以“放弃对列进行扩展的最佳局部最小”技术压缩的，而不是一旦识别出任何不受益于压缩的列就停止。然而，“放弃对列进行扩展的最佳局部最小”技术可以导致更高的整体压缩，甚至与“最佳局部最小”技术相比也是如此，因为它可以识别没有使用“第一局部最小”技术评估的Pset的列，但是与不放弃对列进行扩展的“最佳局部最小”技术不同，它排除了不受益于压缩的列。
在上述任何一种技术中，可以通过对特定列(诸如具有最低基数的列、或者在对其值进行排序后使用最可压缩的列的列)的值(或值ID)进行排序来对表的行进行重新排序。通常，一旦对任何指定的列进行了排序，得到的重新排序将被应用于表中的所有其他列，而不管这些列是否将被压缩，以便保留表中各列之间的值对应关系。
示例6–用于确定在对表行进行重新排序时使用的列排序顺序的示例技术
另一种改进表压缩的技术是考虑用于列的顺序，包括在执行其他技术时将使用的顺序，诸如对要压缩的列的选择，如示例5中所讨论的。列的顺序可能影响所选用于压缩的列、单个列的压缩效率或多个列的压缩效率。例如，可以选择特定的列来对其值进行重新排序，然后将对行的重新排序传播到表中的其他列，无论这些列是否将被压缩。与选择第二列进行排序相比，选择第一列进行排序可以为其他列提供更好或更差的压缩。类似地，选择第二列和后续列以用于排序可能影响整体压缩效率。因此，选择提供较低总体存储成本的列进行排序可能是有益的。
已经描述过的一种列排序技术是通过增加基数来对列进行排序。在这种情况下，具有最低基数的列通常被选择作为提供主要重新排序标准，具有次最低基数的列被选择作为次要重新排序标准等。图8提供了表800的一些数据的示例，该表800具有国家列804、城市列806、时区列808、指示与给定行相关联的车辆是否是四轮驱动车辆(4WD)的列810以及指示车辆颜色的列812的数据。
表800包括多个行820。只要每行820的数据保持在一起，就可以在不改变表800的含义/不改变存储在表中的实际数据的情况下对行进行重新排序。表800可以通过列804-812中的一个或多个的值来排序。为了保留针对给定列的排序，排序可以按序进行，诸如首先按国家排序，然后按城市排序，然后按时区排序，等等。
图8示出了与表800相对应的、但是根据4WD列810的值排序的第一重新排序后的表830。因此，列810的“4WD”值为“T”的行820a是相邻的，并且列810具有“F”值的行820b是相邻的。
注意，用于排序的列810的次序可以提供不同的结果。例如，第二重新排序后的表840对应于表830，但是另外按照国家列804的值进行了排序。第三个重新排序后的表850对应于表830，但是另外按照时区列808的值进行了排序。尽管表800、830、840、850中的所有的行820包含相同的数据，但是它们的顺序不同。表840、850保留了4WD列810的排序，4WD列810具有两个每个长度都为4的游程。然而，按国家对表830进行排序得到国家列804a，其具有一个长度为3的游程、一个长度为2的游程和5个长度为1的游程。按时区对表830进行排序得到时区列808，其包括两个长度为2的游程和八个长度为1的游程。因此，至少对于在本讨论中考虑的可能性，表840可以被识别为比表850更可压缩，因此810、804的压缩顺序可能优于810、808的压缩顺序。
本公开提供了可以用于对行进行排序以改善对表中的列(诸如表800中的列804-812)的压缩的技术。一般地，这些技术试图识别一个或多个排序次序，总体上改进了表的各列中的游程。注意，一旦确定了排序次序，表800中的整个行820根据该次序被重新排序，使得行820中的数据在重新排序后的表840、850中维护——只有行的顺序改变了，而没有任何行的实际内容改变。在至少一些情况下，在表800被重新排序之后，每个列804-812(或这样的列的子集)可以被单独地压缩，并且压缩信息(例如，游程编码信息)可以被逐列维护，包括将压缩信息存储在也包括压缩后的列数据的文件中。此外，此示例6的重新排序技术可以与本公开的其他方面相结合。特别是，列中的表可以首先被划分为主集和次集。主集中的列可以用于确定表的行顺序。但是，得到的行顺序可以被应用于主集中的列和次集中的列两者。
可以用于确定将用于确定行顺序的列的技术将按照升序列基数来进行排序。以表800为例，列804-812分别具有为4、10、5、2和7的基数。因此，使用升序基数技术对列进行排序将使得首先按列810排序，然后按列804排序，接着按列808排序，然后按列812排序，最后按列806排序。
可以用于对列进行排序的另一种技术可以被称为“相关束”技术。相关束技术涉及基于列中数据之间的相关性对列进行分组或排序。例如，以表800为例，可以预期国家列804的行的值可以与城市列806和时区列808的行的值相关。类似地，城市列806可以与时区列808相关。即使这些列804、806、808可能具有某种相关性，一列的值也不一定确定另一列的值。例如，多个城市可以具有相同的名称(例如，巴黎，德克萨斯对巴黎，法国)，因此，尽管“巴黎”可以暗示法国(可能更强烈)或美国(对于德克萨斯)，但是城市列806的值不直接指示国家列804的值或时区列808的值。
某些相关性可能不太直观。在表800的示例中，涉及车辆，并且更具体地涉及车辆的颜色或者车辆是否是四轮驱动的，最初可能看起来车辆的颜色或者是否是四轮驱动的和车辆关联什么国家或城市无关。然而，可能与大量降雪相关联的城市(例如滑铁卢、丹佛、雷诺、布法罗、加米什)或者与四轮驱动车辆可能有用的其他条件相关联的城市(例如伊基托斯)更常见地与四轮驱动车辆相关联，例如迈阿密、帕洛阿尔托或利马。类似地，也可能特定的车辆颜色在一些国家比在其他国家更常见，这因此可以提供至少与颜色和国家的弱相关性。
相关束技术使用这样的见解，即基于列之间的相关性对数据应用排序可以产生比其他类型的次序确定技术更少/更长的游程，至少对于特定类型的数据集是这样的。一般地，相关束技术包括计算数据子集(例如，表的列)之间的相关性、识别满足最小阈值相关性的数据子集、将那些数据子集分组为束、对束内的数据子集进行排序、以及对束进行排序。结果是原始数据集中的数据子集的排列(permutation)或次序(sequence)，诸如列的次序。然后，可以根据所确定的次序、以与在“升序基数”技术的讨论中所述的类似方式对数据集(诸如表的行)进行重新排序。
可以使用任何合适的方法来确定数据之间的相关性，诸如计算Pearson相关系数。图9提供了相关束技术的示例实现方式的伪代码900。
计算相关系数的矩阵。相关系数的矩阵可以是其所有条目都在值1和-1之间的对称矩阵。利用该矩阵，通过将矩阵解释为p个顶点的图来识别相关的列分组，其中p是主列分区中的列数(或者如果表没有被划分为主列和次列，则p是表中的所有列的数量)。图10示出了图8的表800的属性之间的相关性的示例矩阵1000。矩阵1000使用阴影(而不是数值)来表示属性对之间的相关性强度，其中无阴影的正方形指示无相关性或弱相关性，并且增加的阴影密度表示较强的相关性。在这个示例中，可以看到颜色与国家的相关性较弱，并且颜色与其他属性没有相关性。车辆是否是四轮驱动的与城市的相关性较弱，并且与其他任何属性都没有相关性。时区与国家高度相关，并且与城市中度相关。城市与国家中度相关。
导出图(诸如图1050)被划分为完整的子图，诸如子图1054a-1054f。图1050和子图1054中的边可以与边相关联，其中两个顶点(或节点，其可以对应于表的列)之间的边的权重对应于由顶点表示的数据中的值之间的相关性。可以使用阈值θ，并且当相关性低于θ时，图中的边被删除。子图1054a-1054f由剩余的边形成，并用于构建列束。
可以优先处理顶点数较多的完全图。例如，图10在子图1054a、1054c、1054d和1054e中示出国家的列804。因为子图1054d具有较大数量的顶点，所以可以选择子图1054d来定义束，这使得子图1054d的顶点被从其他子图中移除。然后，该过程使得子图1054d成为束，而表的其余列与单列束相关联(例如，存在仅包含颜色的束和仅包含关于车辆是否是四轮驱动的信息的束)。
执行这个过程直到只存在单连通图，并且如上对于表示“颜色”和“四轮驱动”的列所描述的，它们被放置在它们自己的相关束中。在该过程的最后，获得列束集。在每个束内，可以按照升序基数对这些列进行排序。此外，可以按列基数(诸如按给定的束中具有最低基数的列的基数)对束集中的每个束进行排序。
继续图10的示例，在束1054d中，列可以被排序为国家、时区，然后是城市。考虑所有三个束(1054d和“颜色”和“四轮驱动”的单束)，“四轮驱动”具有比束1054d的最低基数(四，针对四个国家)更低的基数(二)，以及比“颜色”的基数(具有为七的基数)更低的基数。因此，列的最终次序是“四轮驱动”、“国家”、“时区”、“城市”和“颜色”。
相关束技术可以产生相对较大的束、或者可以具有各种不同的基数集(即，具有一些基数相对较高的列和一些基数相对较低的列)。如“相关束”示例和图10中所述的，这种效果可以在束1054d中看到，束1054d包括仅具有四个值的“国家”，还具有“城市”，其中每一个值都是唯一的，提供为10的基数，其是表800的最大值，表800仅具有十个行820。单个束中具有各种不同基数的一个结果是，因为束是通过对组中基数较低的列的基数进行升序而排列的，所以基数较低的列可以用于在基数较高的列之后排序。尽管在一些情况下，这种效果仍然可以提供良好的结果，诸如，如果在束内有很强的相关性，而束之间的相关性很小、或者如果只有少数束具有高度相关的数据，而在其他情况下，这种效果可以提供的效果没有使用其他排序技术所能获得的结果好。
继续使用表作为特定的示例，调整数据子集的排序的一种方法是基于组内列的基数将相关束分为更小的束。这样，具有非常不同的基数的列可以被分为单独的组(在一些情况下，单独的组可以包括单个列)。
可以使用各种技术来确定束中的基数何时足够不同、以至于它们应该被分为单独的束。对数分组可以用于提供基于低-高基数来平衡排序的束，同时将相关列保持在同一个束中。图11提供了这种技术的示例的伪代码1100，其被称为“利用对数分组的相关束”。然而，当束应该被分为多个束时，这种技术可以适于使用其他标准，包括基于基数。
如上所述确定相关束，包括在图9的伪代码900中。通过取包括多个列的相关束中的列的基数的下限值对这些列进行分组。例如，具有110个不同值的列将与具有为“2”的值的其他列分组在一起，具有1053个值的列将与具有为“3”的值的其他列分组在一起，等等。可以调整技术，以考虑到所考虑的表中的列的基数的可变性。例如，如果基数更均匀(例如，在10-1000的范围内，而不是在2-10000的范围内)，可能期望基数的差较小使得列被分为单独的束。
再次查看伪代码1100，伪代码返回元组(tuple)，该元组包括排序后的束的数组和一个扁平化的束的数组，表示列排列。如上所述，一旦确定了修改后的束集，给定束中的列可以按基数排序，然后束可以按基数排序，诸如通过基于每个束中具有最低基数的列增加基数。
这种技术可以使用对上述假设的小变化来说明。考虑表800包括1000行，并且列的基数被确定为“四轮驱动”的基数为2，“国家”的基数为50，“城市”的基数为1200，“时区”的基数为10，并且“颜色”的基数为15。假设与上述示例相比，列之间的相关性无变化，只有单个束包含多个列，即束1054d。
现在，当前技术考虑是否应该将束1054d进一步细分为额外的束。基于上面提供的值，“国家”的值将为1，并且将与下限基数值为1的任何其他列分组在一起。“城市”的值将为3，并且将与下限基数值为3的任何其他列分组在一起。“时区”的值为1，并且因此被分组到与“国家”相同的束中。该分析的结果是，束1054c被分为两个束，一个有“国家”和“时区”，而另一个只有“城市”。
然后，可以按照上述方式对产生的束进行排序。首先对“四轮驱动”进行排序，然后对“国家”、“时区”、“颜色”和“城市”进行排序。注意，与使用“相关束”技术所获得的排序相比，这种分组将较高基数的“城市”列作为用于确定行排序次序的最后一列，而不是作为五个排序标准中的第四个。
在一些情况下，列的基数可能不是该列可压缩程度的准确指示符。因此，基于基数对列进行排序的技术在一些情况下可能比其他技术提供的结果差。因此，上述技术可以适配为包括按可压缩性来排序，而不是按基数来排序。因此，“按升序基数来排序”技术可以改为“按升序可压缩性来排序”。对于“相关束”技术，对于束内排序或束的排序中的一个或两个，可压缩性(而不是基数)可以用作排序标准。
对于“利用对数分组的相关束”，可以调整该技术，使得(1)可以在相关束(包括通过基于分组标准划分另一个相关束所形成的相关束)内对列进行排序；或者(2)基于压缩尺寸(而不是基数)对束进行排序。类似地，可以基于压缩尺寸(而不是基于基数)(例如，可以使用压缩尺寸的对数，而不是基数的对数)对束进行划分。
图12提供了如何使用压缩尺寸来代替“利用对数分组的相关束”技术的基数的伪代码1200。该技术总体上类似于“利用对数分组的相关束”技术。然而，在相关束被评估为通过其基数的对数被细分之后，得到的组内的列是按照升序的压缩尺寸(而不是按照升序的基数)来排序的。
示例7–便于检索选定的压缩数据的示例数据结构
本公开提供了一种技术，该技术可以用于以减少所需存储空间的方式存储游程编码信息，但也便于检索表中各行的数据。也就是说，示例4描述了游程编码信息可以以游程存储格式或位置存储格式存储，其中，游程存储格式可以提供更好的压缩，而相比于游程存储压缩数据，位置存储格式通常需要更多的空间，但是允许更容易地检索各个值。
可以使用比特打包(bit-packing)来存储值标识符；此方法使用每个标识符所需的最小比特数。此方法可以用于值标识符、游程和每个列的游程的行位置。换句话说，每一个值标识符都使用相同的比特数进行记录，并且每一个行位置都使用相同的比特数进行编码。存储行位置的游程编码变体的优点在于执行到行位置的值ID映射是有效的。对于行位置pos，可以用时间O(log(nr))来执行识别其值标识符的二分搜索。也就是说，可以搜索行位置的列表，直到定位到包含行位置pos的bin。以图3的表360为例，如果对行位置4感兴趣，我们可以将从位置3开始的bin识别为包含行位置4，因为下一个bin从行位置7开始。
然而，使用存储游程而不是行位置的游程编码，通常需要执行多达pos次添加(addition)，以在给定的行位置处递增地找到适当值。这是因为行位置是相对于先前经编码的行位置而被编码的。也就是说，假设也对行位置7感兴趣，但是我们使用图3的表330进行编码。为了找到位置7的值，必须累加游程的值，直到到达位置7。因此，由于bin 1包含3个位置，已知至少下一个bin游程必须加上3，才能确定位置7是否在下一个bin内。在本示例中，第一游程的bin尺寸或游程为3，第二游程的bin尺寸为4，这指示位置7确实在第二bin中，这允许为位置7确定为1的值ID。可以看出，如果对高的行位置感兴趣，则需要更多次添加，多达感兴趣的行位置的值(假设每一个值ID的游程为1)。
在游程存储中搜索特定的行位置的时间复杂度为O(nr)。因此，由于时间复杂度更低，位置存储游程编码对搜索更友好。一些系统(诸如位于德国沃道夫的SAP SE的SAPHANA)使用位置存储游程编码，以加快对单独的行值的检索，尽管这种技术可能会导致比使用游程存储游程编码更低的压缩。
设b(x)为表示值x所需的比特数。对于相等的游程数，每个行位置以b(nr)个比特编码，而游程以b(longest_run(ci))个比特编码，并且longest_run(ci)始终小于或等于nr。如果存在大量不同的值，则长的游程不太可能存在。因此，对于大量的游程，longest_run(ci)预期会很小。
本公开提供了一种混合数据结构，其对游程存储中的压缩信息进行编码，这可以允许对游程编码数据的更大压缩。但是，辅助数据结构将索引或行引子(primer)存储到游程存储中选定的行位置，从而创建游程存储的虚拟分区。这种辅助数据结构可以被称为“行位置引子存储”，并且可以被存储在存储器中(如同可能被压缩的游程存储可以被存储在存储器中)。混合数据结构可以提供位置存储游程编码的可搜索性和游程存储游程编码的空间可压缩性两者。
可由用户定义的值cap是应用于行位置的最大添加数。当使用基于游程存储的游程编码压缩列时，考虑到辅助结构中相应的行位置，使用计数器。当访问行位置pos处的值标识符时，使用二分搜索找到最近的行位置引子，并且指针跟随到列中的行位置游程，由引子的行位置引导。应用添加来检索正确的行位置。
使用行位置引子是因为添加非常快，因此可以有效地构建合适的行位置。这种方法对基于存储器内的列很友好，因为它用CPU速度来换取更好的压缩。
对在行位置引子执行二分搜索需要对数时间，并且构建行位置最多需要cap次添加。因此，随机访问的时间复杂度为O(log(nr)+cap)，并且行位置引子的空间容量为O(log(nr)*runs/cap)。
图13示出了示例性混合数据结构，包括游程存储1310和辅助数据结构1314，或者行引子存储。游程存储1310类似于图3的游程存储330。辅助数据结构1314存储与由cap值定义的行集合的最后一行相对应的行的行位置引子1318。对于每个行位置引子1318，辅助数据结构1314存储逻辑指针1322，该逻辑指针指向游程存储1310的行1326，该行1326对应于由值cap定义的下一个行集合中的第一行(例如，指向位置组中的第一行)。行组可以被称为位置组(例如，行100-199可以是位置组)，并且与行引子相对应的逻辑指针可以使给定位置组中的第一行成为要分析的下一行(例如，行100的行引子使行100成为逻辑指针被解引用后要分析的下一行)。
作为更具体的示例，考虑表包括500行，并且cap被设置为100行。将为多个cap创建行位置引子1318，直到至少表中的行数被容纳在内。在这种情况下，由于存在500行，因此每个行位置引子1318的500行/100行提供了在辅助数据结构1314中需要五个行位置，其中至少第一行之外的行位置(可以假设从游程存储1310的第一位置开始)与到游程存储的行1326的指针1322相关联。在本示例中，行位置引子1318将对应于0(针对行位置，为行0-99提供指针)、99(为行100-199提供指针)、199(为行200-299提供指针)、299(为行300-399提供指针)和399(为行400-499提供指针)。
当要访问给定的行时，将需要最大cap次添加来访问游程存储1310中该行的值ID。例如，如果指定了行404，则可以搜索辅助数据结构1314以发现行400是行404的最近行位置引子，并且行399的指针可以跟随到游程存储1310(使得要搜索的下一行将是行400)。然后，游程存储1310可以像往常一样搜索行404，但是从行400到行404的迭代将需要最多四次添加，如果从行400到行404的每个游程的长度为1，就会是这种情况。相反，使用传统的游程存储1310，定位行404的值ID可能需要多达404次添加。
示例8–用于确定压缩后的表尺寸的示例技术
如示例5中所讨论的，所公开的技术可以评估表以进行压缩，并且产生将被压缩的列的主集、以及不将(至少使用当前正在考虑的特定压缩技术)被压缩的列的次集。具有压缩列和未压缩列的表可以被表示为两个项的列表。第一项是压缩列的列表，并且第二项是表示未压缩列的列表。
图14示出了用作解释上述表示的示例的示例表1400。对于表1400，列1和2将被压缩，而列3和4将保持未被压缩，整个表可以表示为：
[[(1,3),(3,1),(2,2),(0,1)],[(5,4),(6,3)]],[[1,5,3,2,6,0,4],[4,0,1,2,4,3,5]]]。
成本函数可以使用编码压缩列所需的总比特数，而不是将最小游程数作为成本函数。该表的另一种表示方式(可以更容易地用于尺寸计算)是：
[4,1,3,3,1,2,2,0,1,2,5,4,6,3,*,1,5,3,2,6,0,4,4,0,1,2,4,3,5]。
对于第一主列，包括指示在该主列的数据完整之前应该读取多少对(压缩信息，诸如值ID和游程)的指示符。该指示符后面是以整数对表示的值ID和游程。对所有主列重复该过程。分隔符(诸如“*”)可以用于指示数据中从主列切换到次列的位置。在分隔符之后，次列中的值(未压缩的)被附加到文件中。该指示符的尺寸(8比特)也包括在以上述格式表示表所需的总尺寸中。
示例9–示例表压缩过程
图15是可以使用本公开中描述的一种或多种技术的示例过程1500的流程图。过程1500是在处理关系数据库系统中的表的上下文中描述的，其中表以列存储格式保存。然而，对于其他类型的数据，可以以类似的方式实现过程1500。
在1510，接收未经处理的表1512。未经处理的表1512可以使用字典编码技术1514(诸如示例2中描述的技术)被转换为经字典编码的表1518。注意，过程1500可以用未经字典编码的表来执行，包括使用未经处理的表1512。例如，可以对尚未被字典压缩的表执行游程编码，即使如果同时使用字典编码和游程编码(或另一种压缩技术)，表的整体压缩可能更大。类似地，对未经处理的表1512的任何先前处理都可以在过程1500之外执行，使得过程可以在1514开始。
经字典编码的表1518可以被划分为主列集和次列集，其中次列集可以可选地是空集。也就是说，即使确定所有列都将受益于压缩，仍然可以对列进行评估，以确定应该用于对表的行进行重新排序以提供改进的压缩的列顺序，如将进一步描述的。
将经字典编码的表1518划分为主列集和次列集，可以包括使用示例5中描述的一种或多种划分技术(或启发式技术)1522——第一局部最小1530、最佳局部最小1534和放弃对列进行扩展的最佳局部最小1538，来评估该表。在一些情况下，过程1500被配置为使用特定的主列选择技术。在其他情况下，过程1500可以被配置为评估多种技术，并且可以选择提供最佳结果的技术来使用。在其他的情况下，数据集的性质可以影响应该对该数据集使用哪种主列选择技术。
使用技术1530-1538中的一种或多种分析经字典压缩的表1518的结果是主列集1542。然后可以评估该主列集1542，以确定在对表的行进行排序时应该使用的主列的次序，如示例6中所述的。确定主列集1542的顺序可以包括分析一种或多种排序技术(或启发式技术)1544，包括按照升序基数对集合进行排序1546、使用相关束对集合进行排序1550、使用利用对数分组的相关束对集合进行排序1554、或者使用利用对数分组的相关束和通过升序的压缩列尺寸对主列的至少部分进行重新排序1558。在一些情况下，过程1500被配置为使用特定的主列排序技术。在其他情况下，过程1500可以被配置为评估多种排序技术，并且可以选择提供最佳结果的排序技术来使用。在其他的情况下，数据集的性质可以影响应该对该数据集使用哪种主列排序技术。
尽管过程1500已经被描述为包括主列选择技术和主列排序技术，但是在其他实现方式中，过程仅包括这些技术之一。也就是说，可以对表中的所有列进行排序，而无需评估某些列是否无法受益于压缩。或者，可以确定主列集，但无需考虑通过对主列进行重新排序是否可以获得额外的益处。
在主列选择和重新排序之后，确定主列的顺序1560或次序。在1564，可以使用顺序1560对表的行进行重新排序。通常对表中所有列(主列和次列)以相同的方式对行进行重新排序，因此，即使行顺序与原始表中的顺序不同，表的行信息也被保持。在1568，可以对重新排序后的表的列进行游程编码，包括使用示例7中描述的混合数据结构。
通常，被压缩的每个列都分别被游程编码，并存储在单独的文件中。假设列已经被字典压缩，则该文件可以诸如在标题中包括该列的压缩信息，包括该列的混合数据结构(或用于存储压缩信息的其他格式)，并且可选地包括将与该列一起使用的字典的标识符。压缩的结果产生至少部分压缩的表1572。
示例10–使用所公开的技术选择用于压缩的表列并确定用于对表行进行排序的列顺序的示例实现方式和结果
使用Lemire等人的“Reordering Columns for Smaller Indexes”，InformationSciences—Informatics and Computer Science,Intelligent Systems,Applications:An International Journal,vol.181,no.12,pp.2550-2570,2011中使用的数据集来评估所公开的技术，上述参考文献通过引用、以与本公开不矛盾的程度结合于此。为了便于参考，该参考文献被称为“Lemire”。Lemire中使用了三个数据集：Wikileaks(1193247行，4列)、Census(199523行，42列)和Weather(1015367行，19列)。所公开的技术的实现方式是以具有Pandas 0.25和NumPy 1.17的Python 2.7.15创建的。如示例8中所述地计算压缩列的尺寸。
使用行位置的RLE与使用游程的RLE
在本研究中，针对三个数据集，比较了使用游程与行位置的影响(图16)。在逐个添加列之后，按基数对列进行排序，并确定压缩后的表的尺寸。对于所有数据集，将一个以上的列结果添加到较小的表中。在这两种方法中，当前三分之二的列被压缩时，游程编码在压缩后的表中产生相似的比特数。当只有前几列被压缩时，次列的尺寸决定了压缩后的表的整体尺寸。
用于确定列顺序的最佳局部最小技术(如示例5所述的)被定义为最优点(optimalpoint)。在Wikileaks数据集的最优压缩点(压缩前3列)，使用游程的压缩比使用行位置的压缩小14.17％。对于Weather数据集，最优点是当前13列被压缩时，使用游程的压缩比使用行位置的压缩小0.86％。对于Census数据集，降幅为15.51％。当所有列都被压缩时，在两种方法之间观察到更大的差；对于Wikileaks、Weather和Census数据集，差分别为40.64％、40.14％和23.56％。
这些结果表明，使用游程的压缩优于使用行位置的压缩，因为与位置相比，使用游程的压缩对每个游程进行编码所需的比特数较少。
图17示出了两种压缩方法对主列的压缩的影响。在应用了两种算法之后，确定主尺寸的比率，其中小于1的比率是更理想的。这是对与位置存储的RLE相比、示出游程存储的RLE有多有效的准确预测，因为忽略了次列的同等贡献。
在第一列之后，观察到基于游程的RLE主列的尺寸比基于行位置RLE的尺寸严格地小至少7％。此外，该比率随着列数的增加而单调下降。这可能是因为增加更多的列自然地导致增加更多的游程，这与行位置方法的恒定比特数相比，具有更小的长度并且需要更少的比特数。
主划分
评估了将表划分为主列和次列的各种技术的效果。该评估包括估计通过向主列集添加额外的列所提供的递增的改进，以及向主列集添加额外的列是否降低了整体压缩效率。在评估开始时，主列集的尺寸与次列集的尺寸相比几乎微不足道。然后，在对表中的列进行评估的过程接近结束时，主列集的尺寸最终会变大。
如图18所示，在开始时，与次列集的尺寸减小的稳定速率相比，主列集的尺寸以较小的速率增加。随着更多的列被压缩，在对表中的列进行评估的过程接近结束时(在添加15-19列之间)，主列集的尺寸以比次列集的尺寸减小的速率更大的速率增加。这一结果可归因于值ID位置(locality)的减少。
主选择算法
评估了示例5和6中描述的主列选择算法，即全部压缩(Compress All，CA)、第一局部最小(FLM)、最佳局部最小(BLM)和放弃对列进行扩展(AEC)。在所有这三个数据集中，如图17所示，从无压缩到全部压缩，尺寸首先减小直到全局最小，然后增加。然后，如果选择了图上的最小点，则尺寸已经比两个极端(无压缩或全部压缩)小得多。如图19的表所示，对于Wikileaks数据集，最佳局部最小产生的压缩尺寸为相比于“无压缩”的40.02％，和相比于“全部压缩”的75.40％。
对于Wikileaks和Weather数据集，相应的最佳局部最小产生的压缩尺寸明显小于“全部压缩”和“不压缩”两者的压缩尺寸。Census数据集具有大量成都列(42列)，并且各列之间的值分布可能会有所不同。从图16中，可以观察到1)可以存在多个局部最小，以及2)当添加新的列时，压缩列集的尺寸增加。这种模式可能发生在具有大量的列的表中。在Census数据集中的第一局部最小处停止劣于“全部压缩”，因为算法停止得太早。针对第一局部最小技术，在添加最后一列之后，存在可以提供可压缩性的更多的列。注意，如果放弃任何可以提高压缩(AEC)的列，则可以获得比存在多个列时小得多的压缩尺寸。在Census数据集中，使用AEC方法，与最佳局部最小相比，压缩尺寸可以再减少15.10％。
主排序
图20的表给出了评估不同列排序技术的结果。此表中仅示出了主列尺寸。基线是从最佳局部最小中选择的主列集。相关分组、利用对数分组的相关分组、利用对数分组的相关分组以及通过压缩尺寸技术进行排序，与按照升序基数或降序基数对列进行排序进行比较。使用升序的基数进行排序和相关分组的三种变体提供了大致相似的结果。主列集中的列似乎是压缩的瓶颈。当对Census数据集中主列的所有排列执行压缩时，观察到的最佳排列仅比按照升序基数所得出的排列好3％。通常，因为计算量很大，所以考虑表中主列的所有排列是不切实际的，并且没有证据表明这种穷举方法会提供比按照升序基数来排序明显更好的压缩结果。
然而，应当理解，主列选择技术和列排序技术的益处可以取决于数据集的性质。也就是说，尽管相关束技术的三种变体没有在本研究中评估的数据集上提供显著的优势，但是其他数据集可能具有这样的属性，其中相比于使用升序基数，相关束技术可以提供更好的压缩。
示例11–示例数据库环境
图21示出了可以实现所公开的技术的示例数据库环境2100。数据库环境2100可以包括客户端2104。尽管示出了单个客户端2104，但是客户端2104可以标识多个客户端。一个或多个客户端2104可以是OLAP客户端、OLTP客户端或其组合。
客户端2104与数据库服务器2106通信。通过各种子组件，数据库服务器2106可以处理对数据库操作的请求，诸如存储、读取或操纵数据的请求。会话管理器组件2108可以负责管理客户端2104和数据库服务器2106之间的连接，诸如客户端使用数据库编程接口(诸如Java数据库连接(JDBC)、开放数据库连接(ODBC)或数据库共享库(DBSL))与数据库服务器通信。通常，会话管理器2108可以同时管理与多个客户端2104的连接。会话管理器2108可以执行诸如为客户端请求创建新的会话、将客户端请求分配给现有会话以及认证对数据库服务器2106的访问等功能。对于每个会话，会话管理器2108可以维护存储与会话相关的一组参数的上下文，诸如与提交数据库事务或事务隔离级别(诸如语句(statement)级隔离或事务级隔离)相关的设置。
对于其他类型的客户端2104，诸如基于web的客户端(诸如使用HTT协议或类似传输协议的客户端)，客户端可以与应用管理器组件2110接口。尽管被示为数据库服务器2106的组件，但是在其他实现方式中，应用管理器2110可以位于数据库服务器2106之外，但是与数据库服务器2106通信。应用管理器2110可以启动与数据库服务器2106的新的数据库会话，并以类似于会话管理器2108的方式执行其他功能。
应用管理器2110可以确定请求数据库操作的应用的类型，并在数据库服务器2106处仲裁(mediate)对请求的执行，诸如通过援用(invoke)或执行过程调用、生成查询语言语句或在客户端2104和数据库服务器2106可用的格式之间转换数据。在特定的示例中，应用管理器2110从客户端2104接收对数据库操作的请求，但是不存储与请求相关的信息，诸如状态信息。
一旦在客户端2104和数据库服务器2106之间建立了连接，包括当通过应用管理器2110建立时，通常使用查询语言(诸如结构化查询语言(SQL))来执行对客户端请求的执行。在执行请求时，会话管理器2108和应用管理器2110可以与查询接口2112通信。查询接口2112可以负责创建与数据库服务器2106的适当执行组件的连接。查询接口2112还可以负责确定请求是否与先前缓存的语句或存储的过程相关联，并调用存储的过程或将先前缓存的语句与请求相关联。
至少特定类型的数据库操作请求(诸如以查询语言写入数据或操纵数据的语句)可以与事务上下文相关联。在至少一些实现方式中，每个新的会话可以被分配事务。事务可以由事务管理器组件2114管理。事务管理器组件2114可以负责诸如协调事务、管理事务隔离、跟踪运行和关闭的事务以及管理事务的提交或回滚的操作。在执行这些操作时，事务管理器2114可以与数据库服务器2106的其他组件通信。
查询接口2112可以与查询语言处理器2116通信，诸如结构化查询语言处理器。例如，查询接口2112可以向查询语言处理器2116转发来自客户端2104的查询语言语句或其他数据库操作请求。查询语言处理器2116可以包括查询语言执行器2120，诸如可以包括线程池2124的SQL执行器。查询语言处理器2116可以直接执行对数据库操作或其组件的一些请求。查询语言处理器2116可以将对数据库操作或其组件的其他请求转发到数据库服务器2106的另一个组件。例如，事务控制语句(诸如提交或回滚操作)可以由查询语言处理器2116转发到事务管理器2114。在至少一些情况下，查询语言处理器2116负责执行检索或操纵数据的操作(例如，SELECT(选择)、UPDATE(更新)、DELETE(删除))。其他类型的操作(诸如查询)可以由查询语言处理器2116发送到数据库服务器2106的其他组件。查询接口2112和会话管理器2108可以维护和管理与对数据库操作的请求相关联的上下文信息。在特定的实现方式中，查询接口2112可以维护和管理通过应用管理器2110接收到的请求的上下文信息。
当会话管理器2108或应用管理器2110在客户端2104和数据库服务器2106之间建立连接时，客户端请求(诸如查询)可以(诸如使用查询接口2112)被分配线程池2124的线程。在至少一个实现方式中，线程与用于执行处理活动的上下文相关联。线程可以由数据库服务器2106的操作系统管理、或由数据库服务器的另一个组件管理、或者与数据库服务器的另一个组件结合管理。通常，在任何时候，线程池2124包含多个线程。至少在一些情况下，可以动态地(诸如响应于数据库服务器2106处的活动水平)调整线程池2124中的线程的数量。在特定的方面，线程池2124中的每个线程可以被分配给多个不同的会话。
当接收到查询时，会话管理器2108或应用管理器2110可以确定针对该查询的执行计划是否已经存在，诸如在计划缓存2136中。如果查询执行计划存在，则可以检索缓存的执行计划，并(诸如使用查询接口2112)将其转发到查询语言执行器2120。例如，查询可以被发送到由会话管理器2108或应用管理器2110确定的线程池2124的执行线程。在特定的示例中，查询计划被实现为抽象数据类型。
如果查询不与现有的执行计划相关联，则可以使用查询语言解析器2128来解析该查询。例如，查询语言解析器2128可以检查查询的查询语言语句，以确保它们具有正确的语法，并确认这些语句在其他方面是有效的。例如，查询语言解析器2128可以检查查询语言语句中引用的表和记录是否是在数据库服务器2106中定义的。
也可以使用查询语言优化器2132来优化查询。查询语言优化器2132可以操纵查询语言语句的元素，以允许查询被更有效地处理。例如，查询语言优化器2132可以执行诸如展开(unnest)查询或确定查询中各种操作(诸如语句内的操作)的优化后的执行顺序的操作。在优化之后，可以针对查询生成或编译执行计划。在至少一些情况下，执行计划可以被缓存，诸如在计划缓存2136中，如果再次接收到查询，则可以(诸如通过会话管理器2108或应用管理器2110)检索该计划。
一旦生成或接收到查询执行计划，查询语言执行器2120就可以监督针对该查询的执行计划的执行。例如，查询语言执行器2120可以援用数据库服务器2106的适当子组件。
在执行查询时，查询语言执行器2120可以调用查询处理器2140，查询处理器2140可以包括一个或多个查询处理引擎。例如，查询处理引擎可以包括OLAP引擎2142、联接(join)引擎2144、属性引擎2146或计算引擎2148。例如，OLAP引擎2142可以应用规则来为OLAP查询创建优化的执行计划。联接引擎2144可以用于实现关系运算符，通常用于非OLAP查询，诸如联接和聚合操作。在特定的实现方式中，属性引擎2146可以实现列数据结构和访问操作。例如，属性引擎2146可以实现合并功能和查询处理功能，诸如扫描列。
在特定情况下，诸如如果查询涉及复杂或内部并行化的操作或子操作，则查询执行器2120可以将查询的操作或子操作发送到作业(job)执行器组件2154，作业执行器组件2154可以包括线程池2156。针对查询的执行计划可以包括多个计划运算符。在特定的实现方式中，作业执行线程池2156的每个作业执行线程可以被分配单独的计划运算符。作业执行器组件2154可以用于并行地执行查询的至少一部分运算符。在一些情况下，计划运算符可以被进一步划分和并行化，诸如让操作同时访问同一表的不同部分。使用作业执行器组件2154可能增加数据库服务器2106的一个或多个处理单元上的负载，但是可以改善查询的执行时间。
查询处理器2140的查询处理引擎可以访问存储在数据库服务器2106中的数据。数据可以在行存储2162中以逐行格式存储、或者在列存储2164中以逐列格式存储。在至少一些情况下，数据可以在逐行格式和逐列格式之间转换。由查询处理器2140执行的特定操作可以访问或操纵行存储2162、列存储2164或者行存储2162和列存储2164两者(至少对于特定类型的操作(诸如联接、合并和子查询)而言)中的数据。在至少一些方面，行存储2162和列存储2164可以保存在主存储器中。
持久层2168可以与行存储2162和列存储2164通信。持久层2168可以负责诸如提交写入事务、存储重做(redo)日志条目、回滚事务以及周期性地将数据写入存储器以提供持久数据2172的动作。
在执行对数据库操作(诸如查询或事务)的请求时，数据库服务器2106可能需要访问存储在另一个位置处(诸如另一个数据库服务器)的信息。数据库服务器2106可以包括通信管理器2180组件来管理这样的通信。当应用程序管理器位于数据库服务器之外时，通信管理器2180还可以仲裁数据库服务器2106和客户端2104或应用管理器2110之间的通信。
在一些情况下，数据库服务器2106可以是包括多个数据库服务器的分布式数据库系统的部分。数据库服务器的至少部分可以包括数据库服务器2106的组件中的一些或全部。在一些情况下，数据库系统的数据库服务器可以存储数据的多个副本。例如，可以在多个数据库服务器上复制表。附加地或可替代地，数据库系统中的信息可以分布在多个服务器之间。例如，第一数据库服务器可以保存第一表的副本，并且第二数据库服务器可以保存第二表的副本。在又一个实现方式中，信息可以在数据库服务器之间被划分。例如，第一数据库服务器可以保存第一表的第一部分，并且第二数据库服务器可以保存第一表的第二部分。
在执行数据库操作请求时，数据库服务器2106可能需要访问数据库系统内的其他数据库服务器或其他信息源。通信管理器2180可以用于仲裁这种通信。例如，通信管理器2180可以从数据库服务器2106的组件(或从另一个数据库服务器)接收和路由对信息的请求，并接收和路由回复。
数据库系统2100可以包括压缩管理器2184。压缩管理器2184可以用于压缩数据库系统2100中的数据，包括存储在列存储2164中的数据。特别地，压缩管理器2184可以包括选择组件2188。选择组件2188可以用于评估要存储在列存储2164中的表的列，以确定应该被压缩的主列集，以及可选地应该被未压缩地存储的次列集。选择组件2188可以使用示例5中描述的技术。
压缩管理器2184可以包括排序组件2192。排序组件2192可以确定表的列的顺序，该顺序应当用于跨表列对表的行进行排序，这将为要压缩的一组列提供有益的压缩。排序组件2192可以使用示例6中描述的一种或多种技术。
压缩管理器2184还可以包括并应用算法来压缩数据，包括字典压缩或游程编码。当诸如在查询中请求数据时，查询处理器2140可以使用为相关列存储的压缩信息来定位列存储2164中的相关数据，包括使用图13的数据结构来定位压缩后的列数据中(例如，对于特定行)的特定值。
示例12–使用公开的压缩和数据检索技术的示例操作
图22是用于确定要压缩的数据集的多个适当数据子集的适当数据子集的方法2200的流程图。方法2200可以结合示例5中描述的技术，并且特定的实现方式可以包括确定应该使用游程编码压缩的表的列和应该保持未被压缩的列。
在2204，接收包括第一多个适当数据子集的数据集。在特定的示例中，数据集是表，并且第一多个适当数据子集对应于表的列。每个适当数据子集包括数据集的多个元素，其中，元素与给定适当数据子集中的相应位置相关联。例如，适当数据子集可以包括表的多个行的值。可以对表的列中的数据元素进行排序，使得可以通过在列的相同位置处从列中检索值来重构表的行。
在2208，确定第一多个适当数据子集的基数。基数是指适当数据子集中唯一值的数量，诸如给定列中唯一值的数量。在2212，第一多个适当数据子集通过对基数进行升序来重新排序。在2216，对于第一多个适当数据子集的第二多个适当数据子集的相应适当数据子集，确定第一尺寸。在2220，对于第二多个适当数据子集的相应适当数据子集，使用第一压缩技术压缩适当数据子集，以提供压缩后的适当数据子集。
在2224，对于第二多个适当数据子集的相应适当数据子集，确定压缩后的适当数据子集的第二尺寸。在2228，对于具有小于第一尺寸的第二尺寸的第二多个适当数据子集的相应适当数据子集，将相应适当数据子集添加到要使用第一压缩技术压缩的一组适当数据子集中。
图23是用于确定在压缩数据集的适当数据子集时使用的顺序的方法2300的流程图。方法2300可以使用示例6中描述的技术。在特定的示例中，方法2300可以表示确定表列的顺序，其中，该顺序用于在对表列的至少部分进行压缩之前对表的行进行重新排序。
在2304，接收第一多个适当数据子集。适当数据子集具有第一顺序，并且包括多个数据元素。数据元素与适当数据子集中的位置相关联，并且给定适当数据子集中特定位置处的数据元素与其他适当数据子集中给定位置处的其他适当数据子集中的数据元素相关。例如，适当数据子集可以包括表的多个行的值。可以对表的列中的数据元素进行排序，使得可以通过从列的相同行位置处的列中检索值来重构表的行。
如下确定适当数据子集的第二顺序。在2308，确定第一多个适当数据子集的第一适当数据子集和第一多个适当数据子集的第二适当数据子集之间的相关值。在2312，将相关值与阈值进行比较。在2316，确定相关值满足阈值。在2320，基于确定相关值满足阈值，将第二适当数据子集添加到包括第一适当数据子集的组中。
在2324，使用第二顺序对第一多个适当数据子集的数据元素进行重新排序。在2328，压缩第一多个适当数据子集的至少部分的数据元素。
图24是检索包括多个数据元素的数据集的指定数据元素的值的方法2400的流程图。方法2400可以表示使用图13的游程存储1310和辅助数据结构1314的方法，如示例7中所述的。例如，方法2400可以是检索压缩后的表列的指定行的值ID的方法。
在2404，接收对包括多个数据元素的数据集的第一数据元素值的请求。在2408，确定具有多个数据元素位置的第一位置组，多个数据元素位置包括第一数据元素值。在2412，确定为第一位置组指定的第一逻辑指针值。在2416，解除第一逻辑指针到包括数据元素位置和数据值的第一数据结构的引用。在2420，识别第一数据元素在第一数据结构中的位置。在2424，确定在第一数据结构中为第一数据元素指定的第一值。在2428，响应于该请求，返回第一数据元素值。
示例13–计算系统
图25描绘了可以实现所描述的创新的合适的计算系统2500的通用示例。计算系统2500不旨在对本公开的使用范围或功能范围提出任何限制，因为创新可以在不同的通用或专用计算系统中实现。
参考图25，计算系统2500包括一个或多个处理单元2510、2515和存储器2520、2525。在图25中，该基本配置2530包括在虚线内。处理单元2510、2515执行计算机可执行指令，诸如用于实现示例1-12中描述的特征。处理单元可以是通用中央处理单元(CPU)、专用集成电路(ASIC)中的处理器、现场可编程门阵列(FPGA)或任何其他类型的处理器或处理器的组合。在多处理系统中，多个处理单元执行计算机可执行指令以增加处理能力。例如，图25示出了中央处理单元2510以及图形处理单元或协处理单元2515。有形存储器2520、2525可以是易失性存储器(例如，寄存器、高速缓存、RAM)、非易失性存储器(例如，ROM、EEPROM、闪存等)、或者两者的某种组合，并且可由处理单元2510、2515访问。存储器2520、2525以适于由处理单元2510、2515执行的计算机可执行指令的形式存储实现本文所描述的一个或多个创新的软件2580。
计算系统2500可以具有附加特征。例如，计算系统2500包括存储装置2540、一个或多个输入设备2550、一个或多个输出设备2560以及一个或多个通信连接2570，包括输入设备、输出设备和用于与用户交互的通信连接。诸如总线、控制器或网络的互连机制(未示出)将计算系统2500的组件互连。通常，操作系统软件(未示出)为在计算系统2500中执行的其他软件提供操作环境，并协调计算系统2500的组件的活动。
有形存储装置2540可以是可移动的或不可移动的，并且包括磁盘、磁带或盒式磁带、CD-ROM、DVD或任何其他可以用于以非暂时性方式存储信息并且可以在计算系统2500内被访问的介质。存储装置2540存储实现本文所描述的一个或多个创新的、用于软件2580的指令。
输入设备2550可以是触摸输入设备，诸如键盘、鼠标、笔或轨迹球、语音输入设备、扫描设备或向计算系统2500提供输入的其他设备。输出设备2560可以是显示器、打印机、扬声器、CD刻录机或从计算系统2500提供输出的其他设备。
通信连接2570使得能够通过通信介质与另一个计算实体通信。通信介质传送信息，诸如计算机可执行指令、音频或视频输入或输出、或调制数据信号中的其他数据。调制数据信号是信号的一个或多个特性以在信号中对信息进行编码的方式被设置或改变的信号。作为示例而非限制，通信介质可以使用电、光、RF或其他载体。
可以以计算机可执行指令(诸如那些包括在程序模块中的指令)的一般上下文描述这些创新，这些计算机可执行指令在目标真实或虚拟的处理器上的计算系统中执行。一般地，程序模块或组件包括执行特定任务或实现特定抽象数据类型的例程、程序、库、对象、类、组件、数据结构等。在各种实施例中，程序模块的功能可以根据需要在程序模块之间组合或分离。用于程序模块的计算机可执行指令可以在本地或分布式计算系统中执行。
术语“系统”和“设备”在本文中可互换使用。除非上下文另有明确指示，否则这两个术语都不意味着对计算系统或计算设备的类型的任何限制。一般地，计算系统或计算设备可以是本地的或分布式的，并且可以包括专用硬件和/或通用硬件与实现本文所描述的功能的软件的任何组合。
在本文所描述的各种示例中，模块(例如，组件或引擎)可以被“编码”以执行特定操作或提供特定功能，指示用于模块的计算机可执行指令可以被执行以执行这些操作、使得这些操作被执行或以其他方式提供这些功能。尽管关于软件组件、模块或引擎描述的功能可以作为分立的软件单元(例如，程序、函数、类方法)来实现，但是功能不需要作为分立的单元来实现。也就是说，功能可以被结合到更大或更通用的程序中，诸如更大或通用的程序中的一个或多个代码行。
为了便于呈现，详细的描述使用类似于“确定”和“使用”的术语来描述计算系统中的计算机操作。这些术语是对由计算机执行的操作的高级抽象，并且不应该与由人类执行的行为混淆。与这些术语相对应的实际计算机操作取决于实现方式而变化。
示例14–云计算环境
图26描绘了可以实现所描述的技术的示例云计算环境2600。云计算环境2600包括云计算服务2610。云计算服务2610可以包括各种类型的云计算资源，诸如计算机服务器、数据存储库、网络资源等。云计算服务2610可以是集中式的(例如，由企业或组织的数据中心提供)或分布式的(例如，由位于不同位置的各种计算资源提供，诸如不同的数据中心和/或位于不同的城市或国家)。
云计算服务2610由诸如计算设备2620、2622和2624的各种类型的计算设备(例如，客户端计算设备)使用。例如，计算设备(例如，2620、2622和2624)可以是计算机(例如，台式或膝上型计算机)、移动设备(例如，平板计算机或智能电话)或其他类型的计算设备。例如，计算设备(例如，2620、2622和2624)可以利用云计算服务2610来执行计算操作(例如，数据处理、数据存储等)。
示例15–实现方式
尽管为了便于呈现，以特定的顺序描述了公开的方法中的一些的操作，但是应当理解，这种描述方式包含重新排列，除非在此阐述的特定语言要求了特定的顺序。例如，顺序描述的操作在某些情况下可以被重新排序或同时执行。此外，为了简单起见，附图可能没有示出所公开的方法可以与其他方法结合使用的各种方式。
公开的方法中的任何一个可以实现为存储在一个或多个计算机可读存储介质上并在计算设备(例如，任何可用的计算设备，包括智能电话或包括计算硬件的其他移动设备)上执行的计算机可执行指令或计算机程序产品。有形的计算机可读存储介质是可以在计算环境中被访问的任何可用的有形介质(例如，一个或多个光学介质盘，诸如DVD或CD、易失性存储器组件(诸如DRAM或SRAM)、或非易失性存储器组件(如闪存或硬盘))。作为示例并参考图25，计算机可读存储介质包括存储器2520和2525以及存储装置2540。术语计算机可读存储介质不包括信号和载波。此外，术语计算机可读存储介质不包括通信连接(例如，2570)。
用于实现所公开的技术的任何计算机可执行指令以及在所公开的实施例的实现期间创建和使用的任何数据可以存储在一个或多个计算机可读存储介质上。例如，计算机可执行指令可以是专用软件应用或经由web浏览器或其他软件应用(诸如远程计算应用)访问或下载的软件应用的部分。例如，这种软件可以使用一个或多个网络计算机、在单个本地计算机(例如，任何合适的商业上可获得的计算机)上或在网络环境中(例如，经由互联网、广域网、局域网、客户端-服务器网络(诸如，云计算网络或其他这样的网络))执行。
为了清楚起见，仅描述了基于软件的实现方式的特定选定方面。应当理解，所公开的技术不限于任何特定的计算机语言或程序。例如，所公开的技术可以由用C++、Java、Perl、JavaScript、Python、Ruby、ABAP、SQL、Adobe Flash或任何其他合适的编程语言编写的软件来实现，或者在一些示例中，由诸如html或XML的标记语言或者合适的编程语言和标记语言的组合来实现。类似地，所公开的技术不限于任何特定的计算机或硬件类型。
此外，任何基于软件的实施例(包括例如用于使计算机执行任何所公开的方法的计算机可执行指令)可以通过合适的通信手段上传、下载或远程访问。这种合适的通信手段包括例如互联网、万维网、内联网、软件应用、电缆(包括光纤电缆)、磁通信、电磁通信(包括RF、微波和红外通信)、电子通信或其他这样的通信手段。
所公开的方法、装置和系统不应被理解为以任何方式进行限制。相反，本公开单独地以及以各种组合和彼此的子组合地，针对各种公开的实施例的所有新颖和非显而易见的特征和方面。所公开的方法、装置和系统不限于任何特定的方面或特征或其组合，所公开的实施例也不要求任何一个或多个特定的优点存在或问题被解决。
任何示例中的技术都可以与任何一个或多个其他示例中描述的技术相结合。鉴于可以应用所公开技术的原理的多个可能的实施例，应当认识到，所示实施例是所公开技术的示例，并且不应当被视为对所公开技术的范围的限制。相反，所公开技术的范围包括由所附权利要求的范围和精神所覆盖的内容。

Claims (7)

1.一种用于提高压缩效率的计算系统，包括：
一个或多个存储器；
一个或多个处理单元，其耦合到所述一个或多个存储器；以及
一个或多个计算机可读存储介质，其存储计算机可执行指令，所述计算机可执行指令指定如下操作：
接收包括第一多个适当数据子集的数据集，所述第一多个适当数据子集的每个适当数据子集包括所述数据集的多个数据元素，所述多个数据元素与给定适当数据子集中的相应位置相关联，其中，所述数据集对应于具有行和列的表，并且所述适当数据子集对应于所述列，其中，每个适当数据子集包括所述表的多个行的值；
确定所述第一多个适当数据子集的基数，其中，给定适当数据子集的基数是所述给定适当数据子集中唯一值的数量；
通过升序基数对所述第一多个适当数据子集进行重新排序；
通过对所述第一多个适当数据子集的具有最低基数的适当数据子集的值进行排序来对所述第一多个适当数据子集的值进行重新排序，其中，所述重新排序被应用于所述第一多个数据子集的所有其他适当数据子集，以保留所述第一多个数据子集之间的值对应关系；
对于所述第一多个适当数据子集的第二多个适当数据子集的相应适当数据子集，确定所述相应适当数据子集的第一尺寸，其中，所述第一尺寸对应于表示所述相应适当数据子集所需的比特数；
对于所述第二多个适当数据子集的相应适当数据子集，使用第一压缩技术压缩所述适当数据子集以提供压缩后的适当数据子集；
对于所述第二多个适当数据子集的相应适当数据子集，确定相应压缩后的适当数据子集的第二尺寸；以及
对于所述第二多个适当数据子集的具有小于第一尺寸的第二尺寸的相应适当数据子集，将所述相应适当数据子集添加到要使用所述第一压缩技术压缩的适当数据子集的组，
其中，未被包括在适当数据子集的所述组内的适当数据子集不使用所述第一压缩技术来压缩。
2.根据权利要求1所述的计算系统，其中，所述第一压缩技术包括游程编码技术。
3.根据权利要求1或2所述的计算系统，其中，在确定所述第一尺寸之前，所述列是使用字典压缩来压缩的。
4.一种在计算环境中实现的用于提高压缩效率的方法，所述计算环境包括处理器和耦合到所述处理器的存储器，所述方法包括：
接收包括第一多个适当数据子集的数据集，所述第一多个适当数据子集的每个适当数据子集包括所述数据集的多个数据元素，所述多个数据元素与给定适当数据子集中的相应位置相关联，其中，所述数据集对应于具有行和列的表，并且所述适当数据子集对应于所述列，其中，每个适当数据子集包括所述表的多个行的值；
确定所述第一多个适当数据子集的基数，其中，给定适当数据子集的基数是所述给定适当数据子集中唯一值的数量；
通过升序基数对所述第一多个适当数据子集进行重新排序；
通过对所述第一多个适当数据子集的具有最低基数的适当数据子集的值进行排序来对所述第一多个适当数据子集的值进行重新排序，其中，所述重新排序被应用于所述第一多个数据子集的所有其他适当数据子集，以保留所述第一多个数据子集之间的值对应关系；
对于所述第一多个适当数据子集的第二多个适当数据子集的相应适当数据子集，确定所述相应适当数据子集的第一尺寸，其中，所述第一尺寸对应于表示所述相应适当数据子集所需的比特数；
对于所述第二多个适当数据子集的相应适当数据子集，使用第一压缩技术压缩所述适当数据子集以提供压缩后的适当数据子集；
对于所述第二多个适当数据子集的相应适当数据子集，确定相应压缩后的适当数据子集的第二尺寸；以及
对于所述第二多个适当数据子集的具有小于第一尺寸的第二尺寸的相应适当数据子集，将所述相应适当数据子集添加到要使用所述第一压缩技术压缩的适当数据子集的组，
其中，未被包括在适当数据子集的所述组内的适当数据子集不使用所述第一压缩技术来压缩。
5.根据权利要求4所述的方法，其中，所述第一压缩技术包括游程编码技术。
6.根据权利要求4或5所述的方法，其中，在确定所述第一尺寸之前，所述列是使用字典压缩来压缩的。
7.一个或多个计算机可读存储介质，包括：
计算机可执行指令，当由计算系统执行时，使得所述计算系统执行根据权利要求4-6中任一项所述的方法。
CN202110539890.3A 2020-05-19 2021-05-18 数据压缩技术 Active CN113688127B (zh)

Applications Claiming Priority (2)

Application Number Priority Date Filing Date Title
US16/878,419 2020-05-19
US16/878,419 US11558067B2 (en) 2020-05-19 2020-05-19 Data compression techniques

Publications (2)

Publication Number Publication Date
CN113688127A CN113688127A (zh) 2021-11-23
CN113688127B true CN113688127B (zh) 2024-07-05

Family

ID=75887883

Family Applications (1)

Application Number Title Priority Date Filing Date
CN202110539890.3A Active CN113688127B (zh) 2020-05-19 2021-05-18 数据压缩技术

Country Status (3)

Country Link
US (2) US11558067B2 (zh)
EP (1) EP3913494A1 (zh)
CN (1) CN113688127B (zh)

Families Citing this family (6)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US11558067B2 (en) 2020-05-19 2023-01-17 Sap Se Data compression techniques
US11940998B2 (en) 2022-06-10 2024-03-26 International Business Machines Corporation Database compression oriented to combinations of record fields
US11886409B1 (en) * 2022-08-11 2024-01-30 Sap Se Searchable catalog of columnar numerical data
CN116707538B (zh) * 2023-06-01 2023-12-29 陕西理工大学 基于云边协同的田径运动员信息数据管理方法及系统
CN117112718B (zh) * 2023-10-16 2024-01-26 达文恒业科技（深圳）有限公司 一种车载电脑系统数据快速存储方法
CN117390064B (zh) * 2023-12-12 2024-03-19 天津南大通用数据技术股份有限公司 一种基于可嵌入子图的数据库查询优化方法

Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5680601A (en) * 1994-12-14 1997-10-21 Hewlett-Packard Company Compression system for reducing the occurrence of a literal prefix
CN101311931A (zh) * 2007-05-21 2008-11-26 Sap股份公司 基于值的出现的表压缩

Family Cites Families (30)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US6301394B1 (en) * 1998-09-25 2001-10-09 Anzus, Inc. Method and apparatus for compressing data
US6959300B1 (en) * 1998-12-10 2005-10-25 At&T Corp. Data compression method and apparatus
US8868544B2 (en) * 2002-04-26 2014-10-21 Oracle International Corporation Using relational structures to create and support a cube within a relational database system
US7103608B1 (en) * 2002-05-10 2006-09-05 Oracle International Corporation Method and mechanism for storing and accessing data
EP1504377B1 (en) * 2002-05-10 2011-06-22 Oracle International Corporation Storing and querying relational data in compressed storage format
US8386444B2 (en) * 2006-12-29 2013-02-26 Teradata Us, Inc. Techniques for selective compression of database information
US7769729B2 (en) * 2007-05-21 2010-08-03 Sap Ag Block compression of tables with repeated values
US20090006399A1 (en) 2007-06-29 2009-01-01 International Business Machines Corporation Compression method for relational tables based on combined column and row coding
US9141664B2 (en) * 2009-08-31 2015-09-22 Hewlett-Packard Development Company, L.P. System and method for optimizing queries
US8589451B1 (en) * 2012-05-24 2013-11-19 Sap Ag Systems and methods for generating a common data model for relational and object oriented databases
CN102737132A (zh) * 2012-06-25 2012-10-17 天津神舟通用数据技术有限公司 基于数据库行列混合存储的多规则复合压缩方法
US9792312B2 (en) * 2012-11-27 2017-10-17 Sap Se Row identification column authorization profiles
US10019457B1 (en) 2013-01-22 2018-07-10 Amazon Technologies, Inc. Multi-level compression for storing data in a data store
US20150178811A1 (en) * 2013-02-21 2015-06-25 Google Inc. System and method for recommending service opportunities
CN104937563A (zh) * 2013-04-30 2015-09-23 惠普发展公司，有限责任合伙企业 将数据组块分组到压缩区域中
CN104424314B (zh) * 2013-09-06 2019-06-11 Sap欧洲公司 对列状表数据库的数据库操作
US9753983B2 (en) * 2013-09-19 2017-09-05 International Business Machines Corporation Data access using decompression maps
US10303682B2 (en) * 2013-09-21 2019-05-28 Oracle International Corporation Automatic verification and triage of query results
US20160006663A1 (en) * 2014-07-02 2016-01-07 Telefonaktiebolaget L M Ericsson (Publ) Method and system for compressing forward state of a data network
US10120890B2 (en) * 2015-06-23 2018-11-06 Sap Se Formula-encoded time stamps for time series data
US10303759B2 (en) * 2015-12-03 2019-05-28 International Business Machines Corporation Memory preserving parse tree based compression with entropy coding
US10649965B2 (en) * 2016-11-14 2020-05-12 International Business Machines Corporation Data migration in a networked computer environment
US10762071B2 (en) * 2016-11-29 2020-09-01 Sap Se Value-ID-based sorting in column-store databases
US10599395B1 (en) * 2017-10-11 2020-03-24 Amperity, Inc. Dynamically merging database tables
CN108319714A (zh) * 2018-02-08 2018-07-24 中国人民公安大学 一种基于HBase的列存储压缩方法
CN110825706B (zh) * 2018-08-07 2022-09-16 华为云计算技术有限公司 一种数据压缩的方法和相关设备
US11537571B2 (en) * 2018-09-25 2022-12-27 Salesforce, Inc. Column data compression schemes for scaling writes and reads on database systems
CN110958212B (zh) * 2018-09-27 2022-04-12 阿里巴巴集团控股有限公司 一种数据压缩、数据解压缩方法、装置及设备
US11558067B2 (en) 2020-05-19 2023-01-17 Sap Se Data compression techniques
US11714573B1 (en) * 2021-03-29 2023-08-01 Amazon Technologies, Inc. Storage optimization in a distributed object store

Patent Citations (2)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US5680601A (en) * 1994-12-14 1997-10-21 Hewlett-Packard Company Compression system for reducing the occurrence of a literal prefix
CN101311931A (zh) * 2007-05-21 2008-11-26 Sap股份公司 基于值的出现的表压缩

Also Published As

Publication number Publication date
US11558067B2 (en) 2023-01-17
US12047098B2 (en) 2024-07-23
EP3913494A1 (en) 2021-11-24
CN113688127A (zh) 2021-11-23
US20230103328A1 (en) 2023-04-06
US20210367613A1 (en) 2021-11-25

Similar Documents

Publication Publication Date Title
CN113688127B (zh) 数据压缩技术
Yang et al. Qd-tree: Learning data layouts for big data analytics
CN113227998B (zh) 全面支持自主json文档对象（ajd）云服务的技术
US9697254B2 (en) Graph traversal operator inside a column store
US10380269B2 (en) Sideways information passing
CN108536692B (zh) 一种执行计划的生成方法、装置及数据库服务器
EP3014488B1 (en) Incremental maintenance of range-partitioned statistics for query optimization
US20210256006A1 (en) Hash multi-table join implementation method based on grouping vector
Siqueira et al. The SB-index and the HSB-index: efficient indices for spatial data warehouses
US9298754B2 (en) Query management system and engine allowing for efficient query execution on raw details
US20100235344A1 (en) Mechanism for utilizing partitioning pruning techniques for xml indexes
Chattopadhyay et al. Procella: Unifying serving and analytical data at YouTube
Terlecki et al. On improving user response times in tableau
CN113704300B (zh) 供数据检索方法使用的数据印记技术
Urbani et al. Adaptive low-level storage of very large knowledge graphs
Kvet Relational data index consolidation
US11520763B2 (en) Automated optimization for in-memory data structures of column store databases
Kvet et al. Relational pre-indexing layer supervised by the DB_index_consolidator Background Process
Carter et al. Nanosecond indexing of graph data with hash maps and VLists
Ordonez et al. A survey on parallel database systems from a storage perspective: rows versus columns
CN113742346A (zh) 资产大数据平台架构优化方法
US20230109463A1 (en) Practical method for fast graph traversal iterators on delta-logged graphs
Šalgová et al. The impact of table and index compression
Pirzadeh On the performance evaluation of big data systems
Ttito Amezquita Query co-planning for shared execution in key-value stores

Legal Events

Date Code Title Description
PB01 Publication
PB01 Publication
SE01 Entry into force of request for substantive examination
SE01 Entry into force of request for substantive examination
GR01 Patent grant
GR01 Patent grant