A horizontally partitioned storage layout for columnoriented relational in-memory databases is a popular design choice. One of the reasons for horizontal table partitioning is the increased degree of exibility in data placement, multiprocessing, and physical design decisions. For example, auxiliary data structures such as indexes or lters can be created partition-wise with varying implementations. However, creating indexes per partition can result in a signi cant computational overhead for index lookup operations. In this work, we present a partial indexing idea to overcome this overhead. Our proposed approach creates indexes table-wise, but only tuples of frequently accessed partitions are indexed. Our research is still in progress. For the realization of our partial index, the maintenance e ciency of the underlying index structure is particularly relevant. Thus, in this work, we evaluate di erent index implementations in their lookup speed, maintenance cost, and memory consumption to identify suitable implementations to realize partial indexes. The hash maps Robin Hood (RH) Flat Map and Tessil's (TSL) Sparse Map achieve overall the best evaluation results. Whereas the former is comparatively faster, the latter has a lower memory footprint.
Horizontal partitioning allows to create indexes
partitionwise with varying implementations [
Table 1 shows two exemplary joins that we executed with our research database Hyrise1. Tables in Hyrise are horizontally partitioned into partitions of 65 535 tuples. The depicted joins utilize indexes which are created partition-wise. Both joins have the same predicate, the same indexed base table as left input, and a ltered table as the right input. The right, non-indexed table is referred to as probe table.
In query 19, the number of tuples in the probe table is 2 771 higher than in query 17. Although this number is small compared to the number of tuples in the indexed table of almost 60 million, it results in a crucial additional e ort for 1Source code at https://github.com/hyrise/hyrise 32nd GI-Workshop on Foundations of Databases (Grundlagen von Datenbanken), September 01-03, 2021, Munich, Germany.
Copyright © 2021 for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). TPC-H Query ID
Join predicate l partkey = p partkey l partkey = p partkey
Number of tuples Indexed table the index probing compared to query 17. With the aforementioned partition size, the indexed table consists of 916 partitions. Since indexes are created partition-wise, one equality lookup for each of the 916 created indexes must be executed for each tuple of the probe table to retrieve matching tuples of the indexed table. In total, this results in 1 819 176 equality lookups in query 17 and 4 357 412 in query 19.
Consequently, the index joins' performance depends on the partition count of the indexed data table and scales inversely proportional with it: As the number of partitions increases, so does the number of indexes and the number of lookup operations required.
Our ongoing research focuses on the design and exemplary implementation of a partial indexing strategy to overcome this computational index probing overhead. The contributions of this work are as follows:
Partial Indexes. We introduce an idea of partial indexes to reduce the shown computational index probing overhead. Our partial indexes are to be created tablewise instead of partition-wise, but they store only index entries for frequently accessed partitions.
Index Benchmark Framework. We developed an opensource C++ benchmark framework, which allows researchers to measure the performance of read and write operations of secondary indexes. The evaluation aspects are the latency of insert, delete, lookup and bulk operations and the index memory consumption. Evaluation of In-Memory Secondary Indexes. We present an experimental performance evaluation of different index implementations, including trees, radix trees, and hash maps. We evaluated their read and write e ciency and identi ed index candidates that suite speci cally well for our partial index. 2.
An advantage of partition indexes is the high exibility: For each partition, it can be decided individually whether an index is to be created. This makes it possible to create indexes only for partitions whose data is accessed frequently. Such exibility is not provided with a traditional full table index since it must always be updated when a tuple is inserted into or deleted from the indexed table, or the search-key value of an already indexed tuple is updated. Thus, partition indexes are more e cient in terms of memory consumption as they can selectively index data of a table whereas a full table index contains index entries for all tuples of a table.
Our proposed partial index is a secondary index that breaks the full table index's requirement of indexing a table entirely and can index one or more partitions. Thus, an arbitrary subset of partitions can be indexed. In contrast to tuple-wise indexing of traditional indexes, our partial index's maintenance operations are executed partition-wise. Consequently, index entries are inserted into or deleted from the partial index for the entire data of a given partition. Inplace updates are not considered in this work since our partial index is speci cally designed for insert-only in-memory DBMSs that use multiversion concurrency control.
The Need for Maintenance E ciency. Our partial index
only indexes partitions whose data is accessed frequently to
reduce the memory footprint. As the workload of a DBMS
can change over time [
Consequently, the indexing algorithm required for our partial index is adaptive. Depending on the workload, the algorithm must continuously insert index entries partition-wise into or delete them from partial indexes. The index maintenance e ort of a partial index depends on factors such as the size of the indexed table, the details of the indexing algorithm (e.g., the access classi cation of data as frequently or rarely accessed), the executed database workload, and the underlying data structure of the partial index. In this work, we focus on the latter aspect and identify an index implementation suitable for realizing our partial index.
We developed an open-source benchmark framework2 to evaluate single-attribute in-memory secondary indexes in their lookup speed, maintenance and memory performance. It allows to run certain benchmark cases with di erent index implementations on di erent datasets. The benchmark cases measure the required execution times of the index operations. In selected benchmark cases, the index's memory consumption is additionally measured. The index implementations included in the framework as well as the framework itself are written in C++. 3.1
Unsync ART. The Unsync ART [
MP Judy. Similar to the ART, the Judy Array is an
adaptive radix tree [
Abseil B-Tree. This B-tree, which is part of Google's
opensource collection of C++ libraries called Abseil [
BB-Tree. The BB-Tree [
RH Flat Map. The Robin Hood (RH) Flat Map [
RH Node Map. Similar to the Robin Hood Flat Map, the
Robin Hood Node Map [
PG Skip List. A skip list is a linked list extended by
additional pointers to skip nodes when searching for certain
stored elements [
TSL Robin Map. Similar to the above listed RH Maps,
Tesssil's (TSL) Robin Map [
TSL Sparse Map. Tessil's (TSL) Sparse Map [
STD Hash Map. This map is provided by the C++ standard
library as unordered_map. It \is an associative container that
contains key-value pairs with unique keys" [
Insert (I). The Insert operation creates a new key-value entry in the index. Therefore, the key and the value have to be provided as the operation's input parameters. If an entry with the given key exists in the index, the entry is not added. An exception is the PG Skip List, which overwrites the existing entry.
Delete (D). The Delete operation removes the stored entry that contains a given key from the index.
Equality Lookup (EL). The Equality Lookup expects a key as an input parameter and returns the associated value if the index contains a key-value entry with the given key.
Range Lookup (RL). The Range Lookup operation expects two keys as input parameters, representing a key range, and returns the values of all the stored entries whose key is within the given key range.
Bulk Insert (BI). Inserting a large number of entries is referred to as bulk loading. Since the TLX B+ Tree provides two di erent functionalities in this regard, we distinguish between a bulk insert and a bulk load. The Bulk Insert operation inserts multiple key-value entries into the index without the requirement of the index being empty before.
Bulk Load (BL). Similar to the Bulk Insert, the Bulk Load inserts multiple key-value entries into the index. Unlike the Bulk Insert, the index must be empty before. For example, a bulk load of the TLX B+ Tree means that for a given sorted sequence of index entries, the leaves are created rst, and the overlying levels of the B+ tree are constructed afterward.
The benchmark framework contains the benchmark cases
Insert, Delete, Equality Lookup, Range Lookup, Bulk Insert
and Bulk Load. These are designed to evaluate the index
operations listed in Section 3.2. Due to space limitations,
we only present the Equality Lookup, Delete, and Bulk Insert
cases. The descriptions of all benchmark cases can be found
in the code repository of our benchmark [
Equality Lookup. The time required to execute a given sequence of equality lookups is measured. Before executing and measuring the equality lookups, the index is initialized and a given sequence of index entries is inserted using the insert operation.
Delete. The execution time required to delete a given sequence of index entries using the delete operation is measured. Before the delete operations are executed and measured, the index is initialized and the entire sequence of index entries to be deleted is inserted using the insert operation. The order in which the entries are deleted corresponds to the insertion order.
Bulk Insert. The execution time required to insert a given sequence of index entries using the bulk insert operation is measured. Before the execution and measurement, the index is initialized. Besides, the index's memory footprint is measured. Therefore, the allocated memory is measured before the index's initialization and after inserting the index entries. The di erence of the allocated memory values is considered the index's memory consumption. 3.4
To execute the di erent benchmark cases for the index implementations, di erent data is needed. For all the benchmark cases, a sequence of keys is required as input for the benchmark. This input represents a sequence of index entries, where a single key represents the search-key value and the position of the key, starting at one, represents the tuple identi er (TID). We refer to this input data as entry keys.
We use dense and sparse unsigned integer values as the entry keys to evaluate the index implementations. Additionally, we consider both ascending sorted and unsorted keys. The sorted dense dataset contains sequentially increasing, consecutive integer values, starting at one. For the unsorted dense dataset, the sorted dense keys are randomly shu ed. The unsorted sparse data sequence contains randomly picked, unique unsigned integer values. This sequence is sorted in ascending order for the sorted sparse data.
Additionally, search-key values and ranges of search-key values are required as input data for the Equality Lookup and the Range Lookup experiments, respectively. From a sequence of entry keys, a number of keys is randomly selected as equality lookups data sequence. For the range lookup key ranges, a number of key ranges is selected from a given sequence of entry keys. For each of the selected ranges, the number of qualifying keys is the same.
For our evaluation, we use ve di erent sizes per combination of dense/sparse and ascending/random entry keys. The datasets have the sizes of two, four, six, eight, and ten million entry keys. Furthermore, we use one million lookup operations in the respective benchmark cases. For the range lookups, we used a selectivity of 0.01%. 4.
Since all of the index implementations listed in Section 3.1 support unique keys but not non-unique keys, we only use datasets with unique entry keys in our evaluation. For a given dataset, we ran the benchmark cases using 64-bit unsigned integers as search-keys and TIDs. The measurements reported are the median of 12 runs.
Join operations between foreign and primary keys are an exemplary database use case in which an index for a column with unique unsigned integer values can be utilized. Primary keys are often IDs, which are often represented as unsigned integer values. This applies, for example, when primary keys are surrogate keys.
The index benchmark cases were executed on a machine with four Intel(R) Xeon(R) CPU E7-4880 v2 CPUs on which each socket serves as a non-uniform memory access (NUMA) node. Each NUMA node has 512 GB of DDR3-1600 memory. Benchmarks were bound to a single NUMA node using numactl -N 2 -m 2. The index benchmark was compiled with clang 9.0.1-12 and the options -O3 -march=native. We used the C++ standard library version libstdc++.so.6.0.28. 4.1
Due to space limitations, we only show the benchmark
results for the Equality Lookup, Delete, and Bulk Insert
benchmark cases. The remaining benchmark results can be found
in our code repository [
Equality Lookups. Figure 1 shows the cumulative execution time of one million equality lookups performed with various entry key distributions, entry key orderings, and numbers of entries stored in the index. In each quadrant, the measurements of one data distribution and ordering combination is shown for di erent numbers of stored index entries.
As a reference, we included the lookup duration of the Sorted Vector, which is a dynamic array (std::vector) that stores its values in sorted order. To keep the dynamic array sorted all the time, new values are inserted into the proper position. To nd the position of certain values during a lookup operation, a binary search is performed.
Delete. Figure 2 shows the cumulative execution time of deleting various numbers of index entries using the delete operation. The data characteristics of the entry keys vary in the four di erent quadrants.
Bulk Insert. Figure 3 shows the execution time required to insert various numbers of index entries using the bulk insert operation. The data characteristics of the entry keys vary in the four di erent quadrants.
Simple Vector and Sorted Vector are included as reference. The bulk insert of the Simple Vector consecutively inserts the sequence of given entries to a dynamic array (std::vector). The Sorted Vector additionally sorts the dynamic array after nishing the insertion.
Based on the evaluation measurements, we subjectively categorized these measurements into the categories low (L), moderate (M) and high (H) as shown in Table 3. Since the measurements are execution times and memory consumptions, respectively, lower categories are better. We did not categorize the execution times of range lookups and bulk loads since the former is supported only by the B-tree implementations and the latter only by the TLX B+ Tree.
Non-Competitive Implementations. Executions of di erent benchmark cases showed that the index operations could not be executed in a reasonable time for the BB-Tree and the PG Skip List. Therefore, we excluded these implementations from further evaluation experiments.
Key Findings. As can be seen in Table 3, the RH Flat Map, TSL Sparse Map, and Unsync ART are the only implementations that achieved good or moderate performance on all datasets in the evaluated aspects. Whereas the RH Flat Map shows overall lower operation execution times compared to the TSL Sparse Map, the latter has a lower memory footprint. The Unsync ART achieves an overall moderate performance in the evaluated aspects. Unfortunately, it does not support bulk inserts and provides a faulty delete operation. Apart from the high memory consumption of the TSL Robin Map on all datasets, this hash map achieves overall low operation execution times. In fact, it mostly requires lower equality lookup, delete and bulk insert execution times compared to the RH Flat Map and TSL Sparse Map.
Furthermore, the B-trees, which are the only implementations supporting range queries, generally perform better on sorted data as shown in Table 3. The Abseil B-Tree performs generally better than the TLX B+ Tree. However, even on sorted data, both implementations achieved the highest equality lookup execution time.
Partial Indexes. Stonebraker presented the rst concept of
partial indexes and how they can be used in a DBMS [
Seshadri and Swami extended Stonebraker's idea and
proposed a generalized partial indexing concept, which includes
six di erent strategies that can be used to create partial
indexes [
Database Cracking [
Olma et al. recently proposed an online adaptive
partitioning and indexing algorithm for in situ query processing
engines [
Olma et al.'s algorithm shares similarities with our partial index approach: Both approaches re ne the set of existing indexes automatically and dynamically based on data access frequencies. In addition, both approaches choose the set of data to be indexed on partition granularity. However, while their algorithm creates indexes partition-wise, our approach creates indexes table-wise across selected partitions. Additionally, whereas Olma et al.'s work refers to in situ query processing systems, our approach is designed for in-memory DBMS. Thus, their indexes are created for partitions of raw data les whereas our indexes are to be created for table data stored in main memory.
Index Evaluations and Benchmarks. Xie et al. conducted
an experimental performance evaluation of ve modern
inmemory database indexes [
Alvarez and his fellow researchers presented an
experimental performance evaluation between the ART and the Judy
Array and di erent hash table variants [
Kipf, Marcus and their co-authors developed an
opensource index benchmark framework called Search On Sorted
Data Benchmark (SOSD) [
In this work, we presented the idea of a partial index that is created table-wise but only indexes data of frequently accessed partitions. Using our index benchmark framework, we evaluated the lookup speed, maintenance cost and memory consumption of various index implementations to identify a suitable implementation for partial indexes.
Since our partial indexes are designed to execute maintenance operations on a partition level, the e ciency of bulk operations is particularly relevant. Regarding the equality lookup, delete and bulk insert performance, the TSL Robin Map achieved the best overall results.
As a next step, we plan to implement the proposed partial index in our research database Hyrise so that we can perform end-to-end DBMS performance evaluations afterward.
I sincerely thank my supervisors Jan Kossmann and Markus Dreseler, who supported me intensively and always gave me constructive impulses and detailed, critical feedback. Furthermore, I would like to thank the anonymous reviewers for their valuable feedback.