PaperlayerView exact revision on arXiv

Source-linked AI summary

FITing-Tree: A Data-aware Index Structure

Alex Galakatos, Michael Markovitch, Carsten Binnig, Rodrigo Fonseca, Tim Kraska

arXiv:1801.10207v2cs.DB

TL;DR

Conventional indexes can consume substantial memory, motivating a structure that trades lookup performance against space through a bounded error parameter. FITing-Tree uses piecewise linear segments and a cost model to choose that parameter, achieving comparable performance with orders-of-magnitude lower storage on real-world datasets.

  • Problem

    Indexes for typical OLTP workloads can consume up to 55% of an in-memory DBMS’s total memory, limiting space for new data and intermediate processing.

  • Method

    FITing-Tree uses piecewise linear functions with a tunable bounded-error parameter and a cost model for selecting it under latency or storage requirements.

  • Results

    Across several real-world datasets, FITing-Tree achieves comparable performance to full index structures while reducing storage footprint by orders of magnitude.

  • Takeaways & Limitations

    DBAs can fit index space consumption and lookup performance to a workload using a latency requirement or storage budget.

  • Takeaways & Limitations

    High-write-rate merging algorithms are outside the paper’s scope because they depend heavily on the workload’s read/write ratio.

Abstract

from arXiv · show

Index structures are one of the most important tools that DBAs leverage to improve the performance of analytics and transactional workloads. However, building several indexes over large datasets can often become prohibitive and consume valuable system resources. In fact, a recent study showed that indexes created as part of the TPC-C benchmark can account for 55% of the total memory available in a modern DBMS. This overhead consumes valuable and expensive main memory, and limits the amount of space available to store new data or process existing data. In this paper, we present FITing-Tree, a novel form of a learned index which uses piece-wise linear functions with a bounded error specified at construction time. This error knob provides a tunable parameter that allows a DBA to FIT an index to a dataset and workload by being able to balance lookup performance and space consumption. To navigate this tradeoff, we provide a cost model that helps determine an appropriate error parameter given either (1) a lookup latency requirement (e.g., 500ns) or (2) a storage budget (e.g., 100MB). Using a variety of real-world datasets, we show that our index is able to provide performance that is comparable to full index structures while reducing the storage footprint by orders of magnitude.

1 INTRODUCTION

FITing-Tree addresses the memory overhead of conventional indexes by approximating key-to-position mappings with piecewise linear functions and a tunable error bound. It uses this parameter and a cost model to balance lookup performance and storage, achieving comparable performance with much smaller indexes.

  • 55% of total memory can be consumed by indexes for typical OLTP workloads in a state-of-the-art in-memory DBMS.This overhead reduces space available for storing new data and processing existing data.
  • FITing-Tree compactly captures data trends with piecewise linear functions instead of fixed-size leaf pages pointing directly to data.The approach leverages the underlying distribution to reduce index memory consumption.
  • The tunable error parameter lets DBAs balance lookup performance and index space consumption for a given scenario.The cost model selects an error term from either a lookup-latency requirement, such as 500ns, or a storage budget, such as 100MB.
  • FITing-Tree extends learned-index ideas with bounded worst-case lookup performance, efficient inserts, and paging support.The paper positions these capabilities as differences from initially proposed learned-index techniques.
  • The index stores segment boundaries and slopes in a B+ tree, and existing node-level compression can further reduce its size.This compression is orthogonal to techniques such as prefix and suffix truncation.
  • Across several real-world datasets, FITing-Tree provides similar or sometimes better performance while consuming orders of magnitude less space.The comparison includes existing index structures and is also stated to hold for a worst-case dataset.

2 OVERVIEW

FITing-Tree represents an index as a key-to-storage-location function and approximates it with bounded-error linear segments organized in a tree. The design supports clustered and secondary indexes while reducing the number of indexed structures needed for non-clustered data.

  • 2.1 Function Representation: FITing-Tree partitions key space into disjoint linear segments that approximate the monotonically increasing mapping from keys to storage locations.Each segment stores its starting key and slope to estimate a key’s position.
  • 2.1 Function Representation: Piecewise linear approximation captures data trends while costing less to compute than higher-order functions, reducing construction and insert costs.The approximation is designed to reflect distribution patterns such as changes in IoT activity.
  • 2.1 Function Representation: The error threshold bounds the distance between a key’s predicted and actual position within each segment.The threshold determines how many segments the data distribution produces.
  • FITing-Tree organizes segments in a tree and supports lookup and insert operations for clustered and secondary indexes.The internal tree can also be replaced with another index structure for workloads such as read-only access.
  • 2.2.1 Clustered Indexes: In clustered indexes, variable-sized data segments replace fixed-size B+ tree pages, while leaf nodes store each segment’s slope, starting key, and pointer.Interpolation estimates the position within a segment, followed by a local search for the item.
  • 2.2.2 Non-clustered Indexes: Non-clustered FITing-Trees add a sorted pointer-based indirection layer, introducing overhead but requiring fewer leaf and internal nodes than non-clustered B+ trees.The indirection layer is sorted by the indexed key and points to the corresponding data items.

3 SEGMENTATION

FITing-Tree segments sorted keys with piece-wise linear functions under a tunable maximal-error bound, using ShrinkingCone for efficient construction and bounded worst-case segment coverage.

  • Segment Definition: FITing-Tree partitions key space into variable-sized linear segments and stores segment boundaries and slopes in a B+ tree.This replaces per-key index entries with compact segment summaries while supporting insert and lookup operations.
  • Segment Definition: The maximal-error objective bounds each key’s predicted position relative to its true position, unlike least-square fitting.This bound limits the number of locations that must be searched after interpolation.
  • Algorithm Analysis: error + 1 locations is the minimum covered by a maximal linear segment, bounding the worst-case FITing-Tree size relative to fixed-size B+ tree pages.The paper also reports comparable segment counts between ShrinkingCone and an optimal algorithm on real-world datasets.
  • Segmentation Algorithm: ShrinkingCone greedily scans keys once, extending a segment while the error constraint holds and starting a new segment when a key falls outside the feasible cone.The cone tracks feasible linear functions using an origin point and high and low slope bounds.
  • Segmentation Algorithm: O(n) runtime and small constant memory make ShrinkingCone efficient for index construction, although it is not optimal.For adversarial datasets, its segment count can be arbitrarily worse than an optimal algorithm.

4 INDEX LOOKUPS

FITing-Tree lookups first locate the segment in a B+ tree, then interpolate the key’s position and search a bounded local region within that segment.

  • Point Lookups: A single-key lookup consists of finding the containing segment and then locating the key within that segment.Algorithm 2 expresses these stages as SearchTree followed by SearchSegment.
  • Point Lookups: O(log_b(p)) locates a segment, where b is tree fanout and p is the number of segments rather than individual indexed points.The upper B+ tree indexes segment starts, slopes, and table-page pointers.
  • Point Lookups: pred_pos = (k − s.start) × s.slope estimates a key’s position from its distance to the segment start and the segment slope.The true position is guaranteed to lie within the configured error threshold of this estimate.
  • Point Lookups: O(log_2(error)) bounds the cost of searching inside a segment when binary search is used.Linear, binary, or exponential search may be selected based on hardware properties and the error threshold.
  • Range Lookups: Range queries find one range endpoint with point lookup and then scan forward until keys leave the requested range.This uses contiguous clustered segments or key-sorted indirection for non-clustered indexes.

5 INDEX INSERTS

FITing-Tree supports ordered in-place inserts and buffered delta inserts, preserving the error guarantee while addressing the cost of shifting keys in variable-sized segments.

  • In-place Insert Strategy: In-place insertion locates the target position, shifts elements toward the nearer free end, and preserves sorted order using reserved space.When free space is exhausted, the segment is reapproximated and may be split into new segments.
  • In-place Insert Strategy: error = e + ε divides the specified error into segmentation error e and insert budget ε.The budget lets keys move within reserved page space without violating the overall error bound.
  • Delta Insert Strategy: |s| / 2 keys may need to be moved on average for one in-place insert, motivating amortized buffered insertion.The cost is particularly high for large error thresholds or uniform data producing large segments.
  • Delta Insert Strategy: Delta insertion adds new keys to a sorted fixed-size buffer, then merges and re-segments the data when the buffer fills.The resulting one or several segments are inserted into the upper-level tree while the old segment is removed.
  • Delta Insert Strategy: O(log_b p) + O(buff) is the runtime for locating a segment and adding an item to its buffer.A full buffer adds O(d) re-segmentation cost, where d is segment data plus buffer size.

6 COST MODEL

FITing-Tree’s cost model selects an error threshold to balance lookup or insert performance against index storage, under either a latency requirement or a storage budget.

  • The cost model chooses an error threshold by optimizing lookup latency and space consumption for a given workload.The threshold also affects insert performance, motivating separate latency and storage objectives.
  • 6.1 Latency Guarantee: Estimated lookup latency combines tree navigation, segment search bounded by e, and complete buffer search.The model assumes binary search within the error-bounded segment area and uses the segment count produced for each threshold.
  • 6.1 Latency Guarantee: The latency model treats cache-miss cost c as constant, although caching can change the penalty of random memory accesses.The paper identifies this constant-cost assumption as a simplification.
  • 6.1 Latency Guarantee: A latency-bound workload selects the smallest-footprint index whose estimated lookup latency meets Lreq.The candidate thresholds come from a set E, and SIZE estimates each index’s storage requirement.
  • 6.2 Space Budget: A storage-bound workload selects the smallest error threshold whose estimated index size does not exceed Sreq, thereby targeting the highest performance within budget.SIZE estimates tree storage plus 24B of metadata per segment, including a starting key, slope, and data pointer.
  • 6.2 Space Budget: On real-world datasets, the cost model accurately estimates FITing-Tree size and helps balance latency against storage footprint.

7 EVALUATION

FITing-Tree delivers performance comparable to dense and fixed-page indexes while using substantially less space. Its performance and construction behavior depend on data distribution, error thresholds, insertion strategy, and buffer sizing.

  • Orders of magnitude less space accompanies performance comparable to full and fixed-size-paging indexes.The evaluation covers lookup and insert performance, construction cost, scalability, and internal-tree alternatives.
  • 7.1.2 Lookups.: Four orders of magnitude of space savings lets FITing-Tree match fixed-size paging with 1MB versus over 10GB, while 609MB matches a full index using over 30GB.
  • 7.1.2 Lookups.: Maps reaches full-index performance more quickly than Weblogs and IoT because its data distribution is relatively linear.
  • 7.1.3 Inserts.: Larger errors can reduce insert overhead by producing fewer segments and requiring fewer buffer merges and segmentation operations.This makes FITing-Tree faster than fixed-size paging in some cases.
  • 7.1.3 Inserts.: Delta inserts generally provide the highest throughput above error 100, whereas in-place inserts win at lower errors; low fill factors generally improve in-place performance.Higher-error segments contain more keys, increasing the data moved by in-place insertion.
  • 7.3 Construction Cost: Streaming segmentation can make FITing-Tree construction less expensive than fixed-page B+ tree construction in some initial-loading cases.The streaming algorithm exploits trends to produce fewer leaf-level entries.
  • 7.5 Exp. 5: Data Size Scalability: FITing-Tree closely follows full-index performance as dataset size grows, while full and fixed-page indexes exceed available memory at scale factor 32.
  • 7.4 Cost Models: The latency and size cost models accurately predict their respective quantities, with pessimistic estimates; latency slightly overestimates because caching is excluded.

8 RELATED WORK

Related work spans index compression, partial and adaptive indexes, function approximation, learned indexes, and sparse or hardware-conscious structures. FITing-Tree differs by exploiting data distributions while targeting broad query support and explicit lookup, insert, and size guarantees.

  • Index Compression: FITing-Tree complements existing B+ tree compression techniques, which reduce key representation but retain linear growth with distinct keys.
  • Other Index Structures: Unlike correlation maps, FITing-Tree does not assume an existing index and uses variable-sized paging to model the data.
  • Learned Indexes: Unlike prior learned indexes, FITing-Tree provides strict error guarantees, supports inserts, paging, and a cost model for predictable performance and size.
  • Other Index Structures: Compared with sparse range-oriented structures, FITing-Tree models the underlying data distribution and bounds lookup and insert latency.
  • Partial and Adaptive Indexes: Unlike partial indexes and database cracking, FITing-Tree supports all attribute values and ad-hoc queries without relying on query-driven reorganization.
  • Function Approximation: FITing-Tree applies bounded maximal-error, monotonic, potentially disjoint piecewise approximation to indexing rather than similarity search or unbounded regression compression.

9 CONCLUSION

The paper concludes that FITing-Tree uses a tunable error parameter and cost model to balance index lookup performance against space consumption. Across real-world datasets, it achieves full-index-comparable performance with orders-of-magnitude lower storage.

  • FITing-Tree’s tunable error parameter lets DBAs balance lookup performance and index space consumption.
  • A cost model selects the error parameter from either a lookup-latency requirement, such as 500ns, or a storage budget, such as 100MB.
  • Across several real-world datasets, FITing-Tree achieves performance comparable to a full index while reducing storage by orders of magnitude.

A SEGMENTATION ANALYSIS

The segmentation analysis establishes a minimum segment size for ShrinkingCone and shows that its practical algorithm can be arbitrarily worse than an optimal segmentation algorithm in segment count.

  • ShrinkingCone’s analysis proves a minimum size for segments produced by the algorithm.
  • Although efficient in practice, ShrinkingCone can be arbitrarily worse than an optimal algorithm when minimizing the number of segments.
  • A candidate segment is invalid when the interpolated location error exceeds the specified error threshold.
  • For increasing integer positions, the first point outside a segment implies at least err + 1 locations in the preceding segment.

A.2 ShrinkingCone Competitive Analysis

The analysis shows that ShrinkingCone is not competitive: for a constructed adversarial input, it can produce arbitrarily more segments than an optimal algorithm. The construction yields N + 2 segments for ShrinkingCone but only 2 for the optimal solution.

  • Competitive analysis: ShrinkingCone is not competitive because its segment count can be arbitrarily worse than the optimal algorithm.The paper explicitly proves this worst-case property.
  • Adversarial construction: Given error threshold E = 100, the adversarial input begins with three keys spaced E^2 apart, followed by repeated and nonrepeated keys.The construction then repeats a pattern of keys for N iterations before adding a final key.
  • ShrinkingCone output: ShrinkingCone creates N + 2 segments on this input because repeated keys and spacing force each subsequent segment to contain exactly two keys.Adding the next key would violate the error constraint for a previous key, so the greedy algorithm must split.
  • Optimal output: The optimal algorithm needs only 2 segments: the first key forms one segment, while the remaining input fits within a single linear segment.The line from the second key to the last key stays within error E for every key in the remainder.

B FURTHER EVALUATION

This section broadens the evaluation with additional experiments covering Correlation Maps, range queries, buffer-size effects on inserts, and lookup-latency breakdowns.

  • Evaluation scope: The additional experiments compare FITing-Tree with Correlation Maps.The evaluation includes a dedicated comparison with Correlation Maps.
  • Evaluation scope: The evaluation studies FITing-Tree on range queries involving different query selectivities.Range-query performance is presented as one of the additional experimental dimensions.
  • Evaluation scope: The evaluation also varies buffer size for insert throughput and breaks lookup latency into components.These experiments examine write throughput and the time spent in different lookup steps.

B.1 Correlation Maps

FITing-Tree is compared with Correlation Maps and fixed-size paging, then evaluated for range queries, buffered inserts, and lookup breakdowns. The results show benefits from modeling data distributions with variable-sized segments, while buffer size exposes a read-write tradeoff.

  • Correlation Maps: FITing-Tree, Correlation Maps, and fixed-size paging are compared using lookup latency and index size.The Correlation Maps comparison adapts those methods to clustered primary indexes.
  • Correlation Maps: FITing-Tree represents all integer values from 1 to 100M with a single segment and locates any element using almost no space.Correlation Maps perform similarly to fixed-size-page B+ trees because both use fixed-size partitioning.
  • Correlation Maps: FITing-Tree provides faster lookup performance using a smaller memory footprint than Correlation Maps on 400M Weblogs timestamps.Variable-sized segments better model the Weblogs data distribution than Correlation Maps’ fixed-size bucketing.
  • Range queries: A count aggregate over a range has constant lookup latency because FITing-Tree can subtract the range’s start position from its end position.A sum aggregate must examine every tuple in the range, requiring significantly more work for larger ranges.
  • Buffer-size effects: Larger segment buffers improve write throughput by reducing splitting operations, but excessively large buffers increase lookup latency.The experiment uses the Weblogs dataset with error threshold e = 20,000.
  • Lookup breakdown: FITing-Tree’s fill factor lets a DBA tune the index toward read or write optimization depending on workload.Lookup time is divided between locating the segment and searching its data; smaller FITing-Tree trees reduce the tree-search time.
Loading 1801.10207v2…