{'fraction_non_alphanumeric': 0.05099115584019518, 'fraction_numerical': 0.012808783165599268, 'mean_word_length': 4.443559096945551, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Automatically Finding Optimal Index Structure

Existing learned indexes (e.g., RMI, ALEX, PGM) optimize the internal regressor of each node, not the overall structure such as index height, the size of each layer, etc. In this paper, we share our recent findings that we can achieve significantly faster lookup speed by optimizing the structure as well as internal regressors. Specifically, our approach (called AirIndex) expresses the end-to-end lookup time as a novel objective function, and searches for optimal design decisions using a purpose-built optimizer. In our experiments with state-of-the-art methods, AirIndex achieves 3.3x-7.7x faster lookup for the data stored on local SSD, and 1.4x-3.0x faster lookup for the data on Azure Cloud Storage.

Problem. The performance of these indexes is suboptimal when they operate in an environment different from what they are designed for. We have observed this suboptimality (thus, missed opportunity) as we develop a cloud-optimized document store [13]. Also, see § 2 for a concrete example with B-tree indexes.
Opportunity & Challenge. We observe that we can greatly improve lookup speed by carefully choosing structural parameters such as the number of layers, layer sizes, the types and accuracy of internal regressors, etc. Our intuition is as follows. As depicted in Fig. 1, we should prefer shallow and wide indexes if a storage device has very long latency (round-trip time), because we want to reduce the number of I/O operations. In contrast, if the latency is very small in comparison to bandwidth, tall indexes should be preferred. However, finding an optimal design is non-trivial in practice because there are exponentially many candidates ( § 3.2).  Figure 1: Expected optimal structures by I/O characteristics. Our approach, AutoIndex, can automatically find optimal index structures as well as internal regressors.
Our Approach. We propose a new index builder (called AutoIndex) that can learn the optimal structure in a principled manner by navigating in a high-dimensional design space. Specifically, we formulate a novel optimization problem that expresses an end-to-end lookup time in terms of core design parameters (e.g., the number of layers, the size of each node, regressors, etc.) as well as I/O performance. By solving the optimization problem using our highly parallel search method, we can build a low-latency index for large-scale data. Note that our approach is orthogonal to learned indexes [15,17,18,22,24,41,43], which propose the use of regressors for branching functions (instead of exact pointers). In contrast, this work focuses on optimizing the overall index structure. This work is in line with the recent advances at the intersection of data systems and machine learning [7,8,23,26,28,[31][32][33][34][35][36]45].

MOTIVATION & SCOPE 2.1 Motivation
Our intuition is the following: the structure of an index is crucial for its performance because depending on the system environment it operates on, the optimal index structure can vastly differ. For example, optimal index structures can be different if we store data on network-attached devices instead of local SSD, even if we index the same dataset. We illustrate this with a concrete example. (a) has a lower branching factor (200); thus, it is quicker to retrieve each node while the index is higher. (b) has a greater branching factor (5,000); thus, its height is lower while retrieving each node takes more time. Figure (c) shows that depending on system environments (i.e., Short RTT vs. Fast RTT), different structures can show better performance (note: the latency of "High and Narrow" is used as a unit latency). See the text for the simulation setup.
pointers). Note that while Wide is shallower than Tall, fetching each node of Wide takes longer because its page size is 25× larger. Figs. 2a and 2b depict these structures. Interestingly, neither of these two indexes (i.e., Tall and Wide) is superior to the other; that is, there is no single dominant index structure that offers faster lookup speed in all different system environments. To illustrate this, we suppose two storage devices, ShortRTT and LongRTT. ShortRTT operates with 5 ms latency (RTT) and 100 MB/sec bandwidth. LongRTT operates with 100 ms latency (RTT) and 100 MB/sec bandwidth. That is, their bandwidth is the same, but their latencies are different. (Note that our formulation in § 3 handles more general cases.) Now, we show that (i) Tall offers higher performance than Wide if we store data on ShortRTT, and that (ii) Wide offers higher performance than Tall if we store data on LongRTT. For this, we adopt a widely used formula: (data transfer time) = (latency) + (data size) / (bandwidth). For instance, fetching a single page of the dataset stored on ShortRTT takes 5 ms + 4 KB / (100 KB/ms) = 5.04 ms.
• Tall needs 3 nodes and 1 data page = 3 × (100ms + 4KB / (100KB/ms)) + (100ms + 4KB / (100KB/ms)) = 400.16 ms • Wide needs 2 nodes and 1 data page = 2 × (100ms + 500KB / (100KB/ms)) + (100ms + 4KB / (100KB/ms)) = 310.04 ms Need for Efficient Algorithm. While we use a relatively simple example to illustrate the core intuition, finding an optimal index structure is non-trivial to solve by hand, because there are exponentially many configurations we need to consider. To efficiently find an optimal index, we develop an intelligent learning technique that considers the entire index building as an optimization problem.

Scope of This Work
Read-only Index. We focus on building read-only indexes on a sorted key-value dataset. There are two reasons. First, this is a novel attempt at optimizing the entire index by casting it into a statistical optimization problem. Thus, we aim to ensure at least we can build best-in-class read-only indexes. Second, our long term plan is to integrate our index with write-oriented data systems based on LSM trees [30]. Note that segments of an LSM tree are not updatable; they are only merged occasionally to compose bigger (next level) segments. For these compaction operations, it suffices to build read-only indexes as part of compaction.
Point Lookup. We focus our evaluation on point lookup-fetching a value associated with a search key. There are two reasons. First, by optimizing point lookup, we also optimize range search because they involve essentially the same internal operations-traversing nodes from top to bottom. Second, range search can easily be supported by extending point lookup. To retrieve values for a key range (begin, end), we can find the offset for begin using point lookup, then continue fetching data until we see end.
Persistent Index. We focus on the index we persist on storage (e.g., SSD, NVMe, flash drive), not the index maintained in main memory. This is because we aim to enable faster lookup against largescale data kept in persistent databases (e.g., RocksDB, PostgreSQL, SQLite, etc). For this reason, our cost analysis (for fetching data) must incorporate storage-specific data transfer speed.

INDEX AS STATISTICAL OPTIMIZATION
We build an index by solving a statistical optimization problem. Specifically, our algorithm builds the fastest index for the data stored on a certain storage system, where the storage system is abstracted by the data transfer function ( ). ( ) is the time it takes to retrieve the data (serialized on a storage device; see § 3.3 for its usage). In the rest of this section, we formulate an optimization problem and discuss how to solve it.

Index Class
An index class is a class of indexes we can express. The more general an index class is, the larger the set of indexes that we can represent; however, finding an optimal index can be more computationally · · · · · · · · · · · · Opt 1: Model Type Opt 2: Index Height Figure 3: Index structure and optimization parameters.
expensive. Our index class generalizes hierarchical indexes such as B-trees [10,14] and learned indexes [24], as described below.
An index consists of layers (see Fig. 3). There are two types of layers: regressor layers and the data layer. The data layer contains records sorted by keys. Each regressor layer consists of regressor(s). A regressor outputs a range (start, end) which is the data range (in byte offsets) we need to fetch in the next layer. If the next layer is a regressor layer, we fetch regressor(s); if the next layer is a data layer, we fetch key-value pairs (including the search key).
Querying. First, we fetch the entire root layer (i.e., Regressor Layer 1) containing multiple regressors. We use an appropriate regressor (for the given search key) to obtain an offset range for the next layer. This step continues until we reach the data layer. Note that we fetch the entire range at a time; that is, if there are regressor layers, we fetch + 1 times until we obtain a desired key-value.

Parameter Space
A parameter tuple Θ captures the design considerations for an index. The goal of our statistical optimization is to find the optimal Θ (= Θ * ) that minimizes the end-to-end lookup time ℓ. Θ consists of the following parameters: (1) Number of regressor layers ( 1 , . . . , ). (Note: For convenience, we use +1 for the data layer.) (2) Regressor Type ( = 1 , . . . , ): A regressor layer consists of regressor(s) of the same type (e.g., linear regression, step functions), which we denote by . We search for the optimal regressor type for each regressor layer. (3) Precision ( = 1 , . . . , ) of regressor layers: A regressor outputs a range. While we ensure the range contains an appropriate regressor (in the next index layer) or a desired key-value pair (in the data layer), we must tune the sizes of those ranges, which we achieve via .
In determining , there is a natural trade-off. That is, if we build an accurate regressor (with a fine ), its range output tends to be small, but the size of the regressor itself (and the regressor layer) must be big (e.g., with more coefficients for higher accuracy). Using Θ = ( , , ), we express the end-to-end lookup latency in terms of Θ as described in the next section.

Objective Function for Latency
We express a (tight) upper-bound on the end-to-end lookup time ℓ in terms of Θ and the data transfer function, ( ). Specifically, ℓ is expressed in terms of actual regressor layers ( 1 , . . . , ) created as specified by Θ; here, the size of depends on +1 as well as Θ (because is to obtain the data fetch range for +1 ).
Objective Function. Let (·) be a process for creating a regressor. The created regressor's output range size is expressed by .
where fetches ( , ; +1 ) bytes for +1 For a lookup, we first fetch the entire root layer ( 1 ); then, we subsequently fetch every range output by the latest obtained regressor until the data layer. Thus, ℓ can be expressed as: The goal is to find Θ * = ( * , * , * ) at which the above expression is minimized. We present our parameter search algorithm in § 3.4.

Discussion.
Our objective function is an upper bound because some data may be cached in memory; in these cases, no data transfer is needed. We empirically observed that our approach also delivers strong performance in partially cached scenarios.

Index Build via Parameter Search
We provide a high-level sketch of our parameter search algorithm. We omit theoretical justifications and parallelization techniques. Our optimization is in the form of branch-and-bound algorithmswe branch out to construct the best given (i) already constructed +1 , . . . , +1 and (ii) optimal upper layers (i.e., 1 , . . . , −1 ); then, we bound by pruning candidates. Here, the optimal upper layers are obtained via a recursive call of our algorithm, and the best is evaluated using Eq. (1). There are three features that make our approach logically sound and efficient: (1) Principled search for * : In designing our algorithm, one of the greatest technical challenges is finding the optimal number of layers. Our algorithm does this by asking "does stacking another layer reduce the total lookup time?" based on Eq. (1). This approach makes our algorithm logically sound. (2) Effective enumeration of candidate Θ: Our algorithm is not amenable to gradient-descent-style algorithms for two reasons. First, the parameters for Θ include discrete choices (i.e., integer and regressor type ). Second, the regressor creation process (·) is not always differentiable. Nevertheless, our search algorithm can find almost optimal Θ by effectively navigating in the discrete search space. (3) Highly parallel: While our algorithm examines many different Θ, our total search & build process is highly efficient (comparable to existing learned indexes building) because our algorithm is designed to run in an embarrassingly parallel manner.

EXPERIMENT
We share our latest experiment results. While we continue making further enhancements in our implementation, our current results are strong, with the following key points: (1) AutoIndex's learning algorithm exhibits expected behavior of finding optimal index structure for given system environments ( § 4.2). (2) AutoIndex's lookup speed outperforms state-of-the-art methods on different storage devices ( § 4.3). We present each point after explaining our experiment setup.

Setup
We conduct experiments on Microsoft Azure. Our experiments use a large-scale benchmark dataset.
Compared Methods. We compare AutoIndex against several stateof-the-art index libraries: (1) RMI: RMI [24] is one of the most commonly studied learned index implementations. RMI comes with an accuracy knobour results compare RMI with the highest accuracy. Dataset & Queries. We use the Facebook dataset included in "SOSD: A Benchmark for Learned Indexes" [21]. This dataset has 200 million keys. For querying, we randomly pick a key from the dataset and measure the end-to-end time for retrieving the value associated with the key (for each method we compare). To reduce variance, we report the average over twenty iterations.

AutoIndex Adapts
First, we test if AutoIndex produces different (and properly optimized) index structures according to given system environments.
While there are many internal parameters defining the structure of an index, we specifically examine the number of layers (or equivalently, index height) because its results are easier to understand than other parameters (e.g., size of regressor layers, types of regressors). Expectation: As illustrated in § 2, a shallow index should be preferred if the latency (RTT) is large. Actual: To see if our learning algorithm also exhibits such outcomes, we run AutoIndex for different latency values while the bandwidth is fixed at 134 MB/sec. Fig. 4 shows the results. When the latency is extremely small (i.e., 1 microsecond), the algorithm tells us that a six-layered index delivers the fastest lookup speed.  Figure 5: AutoIndex (ours) delivers significantly faster query latency compared to other state-of-the-art methods. This is because AutoIndex optimizes the entire index according to target system environments.
(from 6 to 2) as we increase the latency, which is an expected result. We compare the actual lookup speed below.

AutoIndex is Fastest
Second, we show that AutoIndex outperforms the other indexes. Our comparison is performed using both local SSDs (small RTT) and Azure Cloud Storage (large RTT). § 4.1 describes the details about the methods we compare and also the dataset we use. Fig. 5 summarizes the results. Fig. 5a compares the lookup time for Small RTT (local disks). AutoIndex is the fastest: it is 3.3×-7.7× faster than other methods. Fig. 5b compares the lookup time for Large RTT (Azure Storage). Again, AutoIndex is the fastest: it is 1.4×-3.0× faster than other methods. This is because AutoIndex can optimize an entire index structure for target system environments.

ONGOING WORK
We are enhancing AutoIndex in several orthogonal directions. First, we are conducting additional theoretical analyses to formally study the optimality of our parameter search process. Second, we are extending our optimization problem to incorporate possible variance in I/O performance. Third, we are improving our builder to stream-process very large data.

ACKNOWLEDGMENTS
We thank the creators/developers of RMI [24], PGM-Index [17], and LMDB [1], who open-sourced their software, which helped us greatly in conducting accurate experiments. This work is supported in part by Microsoft Azure.