A Comparative Study of Compressed, Learned, and Traditional Indexing Methods for Integer Data

The rapid development of learned data structures has significantly enhanced the performance of lookups in database systems, particularly for sorted integer datasets. These data structures have been extensively evaluated in recent years over static and dynamic scenarios through comprehensive benchmarks, such as Search on Sorted Datasets (SOSD) [21, 16] and the Testbed for Learned Indexes (TLI) [32], thus identifying the indexing solutions that perform best under some specific conditions.

In the static context, which is the one of interest in our paper, learned indexes have emerged as the dominant choice due to their low RAM footprint, reduced disk space requirements, and faster lookup times compared to traditional indexes. Despite this prominence, these benchmarks failed to consider other kinds of indexes, such as compressed indexes [8, 7, 19] and compressed+learned indexes [2, 1]. These other data structures are much more interesting because they are “computation friendly”, in that they not only minimize the storage space but also incorporate some specific succinct/compressed indexes that allow fast access to compressed data. Comparing these data structures against the ones already experimented in SOSD [21, 16] and TLI [32] is fundamental to offer a comprehensive comparison, and it is challenging due to the wealth of state-of-the-art technical solutions available. Notable contributions include traditional compressed indexes [26] and newer methodologies leveraging learned compressed indexes [11]. Additionally, known benchmarks often employ unoptimized baselines, which, for example, do not include some recent implementations of traditional indexes (i.e., B-Tree) with SIMD (Single Instruction Multiple Data) operations [29, 15, 17] that achieve exceptional lookup times with no extra space.

The present paper aims to build on these premises by experimentally exploring the performance of learned and compressed indexes more thoughtfully, thus offering new insights into their efficiency and applicability in various data contexts. To reach our goal, we designed a comprehensive benchmarking framework for traditional, learned, and compressed indexes working on static integer datasets that: (i) uses eight real datasets and four synthetic ones of different types (graphs, ratings, time series,…) and size (from 1 to 800 million elements); (ii) includes the implementation of a SIMD-BTree and a SIMD-Sampled-BTree based on [29], that achieve state-of-the-art performance on pointwise queries; (iii) provides scripts to run the experiments and obtain comprehensive reports of its results; (iv) extends the previously existing benchmarks (i.e., SOSD and TLI) in the static context by integrating compressed indexes and including the measurement of other useful metrics (i.e., index size, RAM footprint, build time, and missing items lookup times); and, last but not least, (v) it is extremely easy to be extended with new indexes and datasets.

Through this benchmarking framework, we shed some more light on the performance of learned, compressed, and traditional indexes. Indeed, (1) learned indexes are fast, very efficient in space occupancy, and the best in terms of memory footprint at building time; but (2) existing and our proposed SIMD-variants of BTrees achieve faster lookup times over all of the 12 tested (real and synthetic) datasets using none-to-minimal extra space; and (3) when data compression is mandatory, the best-compressed indexes are LA-vector and EliasFano, but their lookup times are at least 3x slower than that of SIMD-BTrees. We can report in the main article only a few figures/plots that we consider most significant for our discussion because of space constraints, and thus we include a Supplementary Material part and a file named “plot_recap.pdf” in our public code-repository³³3https://github.com/LorenzoBellomo/SortedStaticIndexBenchmark to allow the interested reader finding all experimental figures and further comments.

The paper is organized as follows. Section 2 describes the 12 datasets on which we performed our experiments; Section 3 details our experimental design and settings; Section 4 describes the 15 indexes we tested; Section 5 presents the experimental results conducted on all the described indexes and datasets, and foresees future research directions.

The experiments conducted on the tested indexes used some datasets that varied widely in terms of size, distribution, nature, and other characteristics. Specifically, we considered three types of datasets: synthetic datasets of 32-bit integers, with a size of 50 million elements; real datasets of 32-bit integers, with sizes up to 200 million elements; and real datasets of 64-bit integers, with sizes of 800 million elements for Amzn64 and OSM-Cellids64, and 200 million elements for Wiki64 and Facebook64. All the datasets are downloadable from our public code repository through proper scripts, and they are also available in Zenodo⁴⁴4Link to all datasets: https://zenodo.org/records/15240501.

The choice of their size was dictated both by data availability and by the memory limitations of the machine on which the experiments were executed. In total, our experiments involved 12 datasets comprising roughly $2.6$ billion integers. The detailed description of each dataset is in Section A.1 of the Supplementary Materials for space reasons, but a rough overview is provided in Table 1, and the following bulleted list:

Four 32-bit real datasets:

Two of these datasets are taken from SOSD [21, 16] (i.e., Amzn and Wiki), while the other two are derived from graphs of social or corporate networks, respectively Friendster⁵⁵5Friendster Social Network Dataset: https://snap.stanford.edu/data/com-Friendster.html and CompanyNet, the latter being proprietary to a Sadas client;

Four 32-bit synthetic datasets:

All integers in these datasets are generated synthetically using standard routines. Specifically, three of these datasets used generators from the C++ standard library (i.e., normal, lognormal, and exponential), while the Zipf distribution was generated using a specific script [30];

Four 64-bit real datasets:

All integers in these datasets are taken from SOSD [21, 16] (i.e., Amzn64, Wiki64, OSM-Cellids64, and Facebook64).

As a note, we point out that we have generated two additional datasets to run a preliminary experiment on performance scalability with the dataset size; specifically, we generated a subset of Amzn64 (containing the first 50 million items), and a larger 800 million integer normal-distribution dataset (using the same parameter as the Normal dataset, and still 32 bits unsigned integers).

The experimentation focused on static datasets, where we tested three types of indexes (traditional, learned, and compressed), described in detail in Section 4, and whose results are reported in the file “plot_recap.pdf” in our repository⁶⁶6https://github.com/LorenzoBellomo/SortedStaticIndexBenchmark. For each index, we measured the following metrics:

Disk Space Footprint:

This is the space taken by each tested index, measured in MB⁷⁷7Values in MB were rounded up to the nearest integer.. The results are detailed in the plots of Figures 2, 3. We notice that, for a fair comparison with the compressed indexes, the disk space of the non-compressed ones (i.e., learned and traditional) includes the memory required to store the std::vector containing the data.

Construction Time:

In some applications, it is crucial to have an index ready quickly so that it can be rebuilt fast after a few changes. We measured the time (in milliseconds) required to construct each index to evaluate this issue. The results are shown in Figure 1.

RAM Footprint:

A fundamental metric for assessing the efficiency of an index is the peak internal memory required to construct it. In our experiments, we calculated the maximum and minimum memory peaks. We reported it as the “ratio” with the memory required by the std::vector, also reporting the dataset where these ratios were obtained.

Pointwise Query:

This query evaluated the average time to search for a single element, present or not in the indexed dataset. The average was computed over 1 million distinct queries on each dataset. The sampled distinct queries are fixed for all indexes, and they are chosen as follows: the 1 million query items are sampled uniformly at random from the input, for the experiment on existing items; while they are generated uniformly at random (between the minimum and the maximum key) for the experiment on missing items. Depending on the tested index, the search returns one of the following results: (i) the index or value of the first element greater than or equal to the queried value (Next-GEQ), or a “safe” value indicating that no element greater than or equal to the query exists; (ii) an approximation (with error) of the position of the Next-GEQ in the vector, typical of learned indexes. In this second case, we ensure timing consistency by counting the cost of searching the exact position via the lower_bound function of the C++ standard library. Choosing to use lower_bound for the last-mile search has an impact on the final query results timings, but we decided to use it because of the following reasons: (i) the binary search is the default option for all the learned indexes that provide an approximate position; (ii) the implementation of the lower_bound function of the C++ standard library is compiler dependent, making it very hard to reliably benchmark; (iii) Marcus et al. [21, 16] analyzed the impact of the search algorithm in their work on SOSD, testing linear, binary, and interpolation search, and found that interpolation search and binary search obtain comparable results (difference of $\sim 2\%$), while linear search performed worse; (iv) the main point of PGM++ [20] is to improve the PGM-index by changing the search algorithm for all the PGM layers, obtaining results that, as seen in Section 5, are in line with those of PGM-index. For those reasons, we deemed this part of the benchmark too focused on the task of “measuring search time”, rather than focusing on the indexes, so we decided to ignore it. The results of these experiments are shown in Figures 2, 3, and in Figure 4 of the Supplementary Materials.

Range Query:

This benchmark evaluates the time required for each index to perform a random access on the indexed data and a scan of the subsequent $x$ elements, with $x=10,100,1K,10K$. Time was averaged on $\mathrm{100\hspace{0.17em}000}$ range queries. This experiment was run on four selected datasets (i.e., CompanyNet, Amzn, Wiki, and Facebook64) and is particularly useful for assessing the performance of compressed indexes and of the SIMD-BTree (which permutes the data). In fact, the other indexes rely on the std::vector, and thus their scan performance depends on this latter, so we refer to it in the plots. The plots are reported in Figure 5 in the Supplementary Materials and in the file “plot_recap.pdf” in our repository.

The final time performance of the construction, range, and pointwise queries was computed by repeating each experiment 10 times and then averaging the individual results.

Table 2 summarizes the key information about the tested indexes. Specifically, it shows the citations of relevant works for each index, the year of the last update to the corresponding library (to assess its “maintenance vitality”), the space required to represent the original data, the space needed to construct the indexing structures, and the support for the “Rank” operation (indicating whether it is directly available in the library or easily derivable).

The selection of the test indexes was based on the state of the art in this field [27, 18, 22, 12, 20, 31, 6, 2, 1, 13, 25, 24, 19] and the most relevant benchmarks found in the literature, as previously mentioned (that is, SOSD [21, 16] and TLI [32]). Regarding the state-of-the-art, three main families of indexes can be identified: (i) Traditional and/or Baseline Indexes, (ii) Learned Indexes, and (iii) Compressed Indexes.
It is important to note that while compressed indexes encapsulate both the index and the input data within a space smaller than a std::vector (hence, they could also be called compressed self-indexes), traditional and learned indexes occupy the space of the std::vector plus the extra space needed to store the index, although this extra space is often minimal. These solutions are particularly interesting in contexts where the input data vector is read-only and multiple indexes are required for different primary keys, or when the input data is large and stored in external memory while the (small) index is kept in internal memory to support fast searches.

In the next Sections, we describe briefly all the tested indexes. For a more detailed description, we refer the readers to Section A.2 of the Supplementary Materials.

The server used for the experiments has 512 GB of RAM and an Intel(R) Xeon(R) Gold 6238R CPU at 2.20 GHz, with a total of 56 cores, running Ubuntu 22.04 LTS on an x86-64 architecture. The following precautions were taken to minimize interference with external factors and ensure a fair benchmarking environment: the CPU frequency was set to the nominal frequency, via the “cpupower” command, and “hyperthreading” was disabled.

One of the key contributions of our paper is that we packaged the benchmarking code²³²³23Based on the library Google Benchmark: https://github.com/google/benchmark and datasets into a publicly available repository²⁴²⁴24https://github.com/LorenzoBellomo/SortedStaticIndexBenchmark, with the goals of:

• $\mathrm{■}$

  making it extremely easy to run the benchmark and reproduce our experimental results through a set of bash scripts that aid in installing, downloading the sorted datasets, setting up all the RMI models, compiling, and finally running the experiments;

• $\mathrm{■}$

  allowing the easy generation of consistent and valuable plots/reports. We also provide a LaTeX  file that generates a visually consistent report (like the file “plot_recap.pdf”);

• $\mathrm{■}$

  allowing users to include additional indexes and datasets in the benchmark easily. Specifically, indexes can be added by just integrating it to the CMakeLists file, creating a simple interface file with some simple methods (e.g., build, next-geq), and registering the benchmarks to run.

This article will not explain all the details on running the benchmark because of space constraints, but they will be available in the repository’s README file. Moreover, in this section, we report only a subset of the plots and tables (see Figures 1, 2, 3), since the complete set of results is provided in the Supplementary Materials at the end of this article and in the file “plot_recap.pdf” made available in our public repository (see footnote 24).

The following pages present the experiments conducted on all the indexes described in the previous Section 4. Some figures are missing for LA-vector because of errors on some datasets, for Roaring because of its limitation to run only on non-duplicate datasets, and for EliasFano because it fails to run on three datasets.

Let us now start commenting on the construction time using Wiki as a reference dataset (results tend to be consistent). Figure 1 shows that all indexes require negligible time to index 200M elements (around or less than 2 seconds), except for (in decreasing time cost): the “opt” version of LA-vector, ALEX, $\gamma$-code and $\delta$-code vectors, EliasFano, FAST, and PLEX.

We also measured the memory footprint used during the construction of each index, obtaining the following results (expressed as a ratio to the one needed by std::vector):

• $\mathrm{■}$

  PLEX, PGM-index, PGM++, EliasFano: require a footprint that does not exceed three times that required by std::vector (specifically, 1x–3x).

• $\mathrm{■}$

  SIMD-BTree, SIMD-Sampled-BTree, $\gamma$-code and $\delta$-code vectors, CSS-Tree: require a footprint not exceeding five times that of std::vector (specifically, 1x–5x).

• $\mathrm{■}$

  LA-vector uses a variable amount of memory depending on the configuration used. When “bpc” is fixed, the maximum RAM required is $15.5$x, while the minimum is $2$x (on the OSM-Cellids64 and Wiki64 datasets obtained with bpc set to $12$ and $6$ respectively). On the other hand, the process of obtaining the “opt” version of LA-vector is more memory-intensive, with a peak RAM consumption exceeding $100$x on Facebook64.

• $\mathrm{■}$

  ALEX ranges from a minimum of $5.6$x on Wiki64 to $10.7$x on CompanyNet.

• $\mathrm{■}$

  FAST has a RAM requirement that varies from a minimum of $3.4$x on CompanyNet, to a maximum of $5.6$x on Books64.

• $\mathrm{■}$

  Roaring is usually lighter but has a high peak on the Amzn64 dataset, needing $19.4$x.

Let us now turn our attention to the time and space performance of the indexes on pointwise queries, referring the reader to the details in Figures 2 and 3 (and Figures 4 in the Supplementary Materials). In Figure 2, the red bar represents the time-space performance of std::vector, which can be seen as the reference being the space taken by the input data. The compressed indexes are on its left; to its right are the traditional indexes, the learned indexes, and our two SIMD-BTrees. On the other hand, Figure 3 provides a different visual representation of these results by using a two-dimensional time-space plot, highlighting the Pareto curve (more comments in Section 5.1).

We can observe that the SIMD-BTrees (blue and green bars) significantly outperform all the traditional indexes, and also obtain better time performances on pointwise queries than all learned indexes on all datasets, with only PLEX, RMI, and ALEX obtaining similar results in some experiments. In the case of compressed indexes, the situation is more unstable, as different datasets tend to show significantly different performance patterns. Nevertheless, the indexes that tend to obtain the best results on average are EliasFano (Pareto-optimal in 8 out of 12 datasets), and LA-vector (Pareto-optimal in 7 out of 12 datasets).

Table 3 shows a compact view of the best-performing indexes on each dataset. For a deeper analysis of the results, we refer the reader to Section A.3 of the Supplementary Materials, whereas all plots are available in the “plot_recap.pdf” file on our code repository. We highlight that the repository contains plots showing the time performance for increasing the dataset sizes (Amzn64 with 50M–800M items and Normal with 50M–800M items). These plots show that the performance of indexes tends to have a consistent slowdown (up to 2x) as the dataset size increases (up to 16x). As future work, we plan to further extend the dataset sizes.