Faster Compressed Indexes On Next-Generation Hardware

软件索引加速了商业分析、机器学习和数据科学中的应用。它们通常决定大数据应用程序的性能。高效的索引不仅提高了延迟和吞吐量，而且还减少了能源使用。许多索引节约地使用内部内存，以便关键数据保持在处理器附近。还希望直接处理压缩数据，以避免潜在有害的解码过程。因此，我们使用轻量级压缩策略，针对速度进行了优化。*我们对位图索引感兴趣。我们可以在很多流行的系统中找到它们：Oracle、ApacheHave、ApacheSpark、Druid、ApacheKylin、ApacheLucene、Elastic、Git等等。它们是数百万人每天使用的系统(如维基百科或GitHub)不可或缺的一部分。*我们的长期计划有三个研究轴：*(1)追求现有位图索引的优化，就像它们在当前系统中使用的那样。这些系统中的许多都依赖于咆哮或EWAH位图，这两种格式都是我们开发的。我们计划在支持高级SIMD(单指令、多数据)指令的处理器(如AVX2和AVX-512系列)上将其中一些索引的性能提高一倍。*(2)继续用我们的整数压缩技术打破速度纪录。我们关注的是整数的排序列表，因为它们经常出现在B+树、倒排索引和压缩位图索引中。最近几年，我们证明了我们可以每秒解码数十亿个整数，同时将压缩比保持在接近香农熵给出的极限。然而，我们使用了最新处理器的所有功能，但只有一小部分。我们将在最近的服务器处理器上创造新的性能记录，同时压缩得更好。我们还将使用直接在压缩数据上操作的排名、选择、合并、更新和插入功能来加速应用程序。最后，我们将把这项工作应用于数据库引擎(例如，upscaledb)和大数据系统(例如，ApacheParquet、Druid、ApacheSpark)。*(3)开发一种新的位图索引格式，它在内存使用和原始速度方面都超过了最先进的技术。目前，最好的格式之一是咆哮：它被广泛采用，速度快，而且占用内存很少。我们试图设计一种新的格式，在提高速度的同时，使用比咆哮更少的内存。虽然提供更好的压缩相对容易，但要在提高查询性能的同时做到这一点却是一个真正的挑战。这个研究轴直接建立在前两个轴上。

Software indexes accelerate applications in business analytics, machine learning, and data science. They often determine the performance of big-data applications. Efficient indexes not only improve latency and throughput, but they also reduce energy usage. Many indexes make parsimonious use of internal memory so that critical data remains close to the processor. It is also desirable to work directly on the compressed data, to avoid potentially harmful decoding passes. Thus, we use lightweight compression strategies, optimized for speed.******We are interested in bitmap indexes. We find them in a wide range of popular systems: Oracle, Apache Hive, Apache Spark, Druid, Apache Kylin, Apache Lucene, Elastic, Git and so forth. They are an integral part of systems—such as Wikipedia or GitHub—used by millions of people every day .******Our long-term plan has three axes of research:******(1) Pursue the optimization of existing bitmap indexes, as they are used in current systems. Many of these systems rely on either Roaring or EWAH bitmaps, two formats we produced. We plan to multiply the performance of some of these indexes on processors supporting advanced SIMD (single instruction, multiple data) instructions such as those of the AVX2 and AVX-512 families.******(2) Continue to break speed records with our integer-compression techniques. We focus on sorted lists of integers, as they frequently appear in B+-trees, inverted indexes and compressed bitmap indexes. In recent years, we showed that we could decode billions of integers per second while maintaining compression ratios close to the limit given by Shannon's entropy. Yet we used all but a fraction of the features of the latest processors. We will establish new performance records on recent server processors while compressing even better. We will also accelerate applications with rank, select, merge, update and insert functions operating directly over the compressed data. Finally, we will apply this work to database engines (e.g., upscaledb) and big-data systems (e.g., Apache Parquet, Druid, Apache Spark).******(3) Develop a novel bitmap index format that outclasses the state of the art in both memory usage and raw speed. Currently, one of the best formats is Roaring: it is widely adopted, fast and it uses little memory. We seek to design a new format that uses even less memory than Roaring while improving the speed. Though it is relatively easy to offer better compression, doing so while improving query performance represents a real challenge. This research axis builds directly on the first two axes.