Transparent Compression for General-Purpose Programming Languages

无损压缩是存储、传输或处理任何大小和类型的数据集时的关键优化技术。压缩允许管理比主存储介质更大的数据集，并减少了从物理模拟到机器学习模型再到传感器数据管理等应用程序中数据访问的带宽需求。一些压缩方案允许直接在压缩数据上执行计算，与未压缩数据相比通常降低计算复杂度-这种方案通常被称为“轻量级”。例如，对游程长度编码（RLE）阵列中的值求和需要按照压缩输入的大小的顺序进行努力，即，通常显著小于未压缩的输入。类似地，关系选择和连接可以在字典压缩关系的字典或参考框架编码列中的最小值上进行预过滤。实现直接对压缩数据工作的算法是具有挑战性的：计算必须与（解）压缩代码紧密集成，实现中的效率低下很容易超过数据传输或处理性能方面的好处。因此，大多数轻量级压缩方案是定制的，即，为特定的、易于理解的领域（如关系数据库、图像处理或线性代数）开发和调整。虽然最先进的是手动实现它们，但实际上所有轻量级压缩方案都可以表示为原始变换序列，例如行程长度编码（RLE），字典压缩或霍夫曼编码。这种“压缩管道”的例子是PFOR-delta（在Vector DBMS中）、Vertipaq（在Microsoft SQL Server中）或Compressed-Sparse-Row矩阵表示（在许多线性代数包中）。其次，这些方案与特定的数据/处理模型（关系代数，线性代数等）相关联。第三，也是最重要的一点，实现工作量很大，因为每个应用程序都需要从头开始实现压缩。不出所料，许多可以从压缩中受益的应用程序都回避了这种实现工作：特别是对于用Python或R等语言编写代码的领域科学家来说，低实现工作量优先于效率。我们的愿景是让面向性能的压缩的好处适用于上述少数几个应用程序。为此，我们将开发一个代数框架，用于在通用编程语言中表示和优化定制的压缩方案。开发人员将压缩方案表示为集合上的注释，而不是将数百行与压缩相关的代码“编织”到应用程序的逻辑中。后端透明地转换对向量进行操作的代码，以利用压缩策略。这使得即使是非专家也可以实现定制的压缩方案。为了进一步简化接口，我们将实现一种完全自动化的方法，使用基于成本的优化来确定程序，数据集和硬件平台的最合适的压缩方案，而不是要求显式指定。

Lossless compression is a key optimisation technique when storing, transmitting or processing datasets of any size and kind. Compression allows managing datasets larger than primary storage medium and reduces the bandwidth need for data access in applications ranging from physics simulations to machine learning models to sensor data management. Some compression schemes allow computation to be performed directly on compressed data, often reducing computational complexity compared to uncompressed data - such schemes are commonly called "lightweight". For example, summing values in a Run-Length-Encoded (RLE) array requires effort in the order of the size of the compressed input, i.e., usually significantly less than the uncompressed input. Similarly, relational selections and joins can be prefiltered on the dictionary of a dictionary-compressed relation or the minimum-value in a frame-of-reference encoded column.Implementing algorithms to work directly on compressed data is challenging: the computation has to be tightly integrated with the (de-)compression code and inefficiencies in the implementation can easily outweigh benefits in data transfer or processing performance. Consequently, most lightweight compression schemes are bespoke, i.e., developed and tuned for specific, well-understood domains such as relational databases, image processing or linear algebra. While the state-of-the-art is to implement them manually, virtually all lightweight compression schemes can be expressed as sequences of primitive transformations such as Run-Length-Encoding (RLE), dictionary compression or Huffman-coding. Examples of such "compression pipelines" are PFOR-delta (in the Vector DBMS), Vertipaq (in Microsoft SQL Server) or the Compressed-Sparse-Row matrix representation (in many linear algebra packages).However, there are three fundamental problems with the state of the art: first, there is no principled way to assemble these pipelines. Second, these schemes are tied to a specific data/processing model (relational algebra, linear algebra, etc.). Third, and most importantly, the implementation effort is high as every application needs to implement compression from scratch. Unsurprisingly many applications that could benefit from compression shy away from that implementation effort: in particular for domain-scientists writing code in languages like Python or R, low implementation effort takes precedence over efficiency.Our vision is to make the benefits of performance-oriented compression available to applications beyond the mentioned few. For that purpose, we will develop an algebraic framework for the representation and optimisation of bespoke compression schemes in general-purpose programming languages. Instead of "weaving" hundreds of lines of compression-related code into an application's logic, developers will express compression schemes as annotations on collections. The backend transparently transforms code that operates on the vector to take advantage of the compression strategy. This allows even non-experts to implement bespoke compression schemes. Simplifying the interface even further, we will implement a fully automated approach that determines the most appropriate compression scheme for a program, dataset and hardware platform using cost-based optimisation rather than requiring to have it explicitly specified.