Fast Updates on Read-Optimized Databases Using Multi-Core CPUs

Jens Krueger; Changkyu Kim; Martin Grund; Nadathur Satish; David Schwalb; Jatin Chhugani; Hasso Plattner; Pradeep Dubey; Alexander Zeier

Source-linked AI summary

Fast Updates on Read-Optimized Databases Using Multi-Core CPUs

Jens Krueger, Changkyu Kim, Martin Grund, Nadathur Satish, David Schwalb, Jatin Chhugani, Hasso Plattner, Pradeep Dubey, Alexander Zeier

arXiv:1109.6885v1Sep 30, 2011cs.DB

TL;DR

Read-optimized column stores must absorb transactional updates while periodically merging delta data into compressed main storage, making merge overhead a central challenge for mixed workloads. The paper analyzes 12 SAP Business Suite customer systems and develops a linear-time, multi-core-aware merge algorithm. The resulting implementation achieves a 30× speedup over unoptimized serial code and supports transactional enterprise workloads while retaining read-optimized query performance.

Problem
Differential updates require periodic online merging of delta and compressed main partitions, limiting update performance in systems combining transactional and analytical workloads.
Method
The paper analyzes real enterprise systems and develops a linear-time online merge algorithm with multi-core-aware cache and parallelization optimizations.
Results
30× speedup over unoptimized serial code is reported for the optimized merge implementation.
Takeaways & Limitations
The merge algorithm enables in-memory column stores to execute transactional enterprise workloads while retaining high read performance for mixed analytical queries.
Takeaways & Limitations
The prototype omits compression techniques that modify tuple order because they introduce dependencies and limit scalability.

Abstract

from arXiv · show

Read-optimized columnar databases use differential updates to handle writes by maintaining a separate write-optimized delta partition which is periodically merged with the read-optimized and compressed main partition. This merge process introduces significant overheads and unacceptable downtimes in update intensive systems, aspiring to combine transactional and analytical workloads into one system. In the first part of the paper, we report data analyses of 12 SAP Business Suite customer systems. In the second half, we present an optimized merge process reducing the merge overhead of current systems by a factor of 30. Our linear-time merge algorithm exploits the underlying high compute and bandwidth resources of modern multi-core CPUs with architecture-aware optimizations and efficient parallelization. This enables compressed in-memory column stores to handle the transactional update rate required by enterprise applications, while keeping properties of read-optimized databases for analytic-style queries.

1. INTRODUCTION

Read-optimized databases accumulate writes in a delta partition that must be periodically merged with compressed main storage, creating update overhead. The paper analyzes enterprise workloads and proposes a multi-core-aware online merge algorithm that achieves a 30× speedup over unoptimized serial code.

1. INTRODUCTION: Differential updates require periodically uncompressing, merging, and recompressing main storage during regular system load.The delta partition supports writes, but its accumulated changes must be merged without downtime.
1. INTRODUCTION: Frequent merging keeps the write-optimized structure small and read performance stable, but increases update overhead.The paper identifies insert rate and merge speed as the two limits on update performance.
1. INTRODUCTION: Analyses of 12 SAP Business Suite customer systems motivate an online merge design for enterprise workloads.The authors report approximately 20 monthly merge hours and about 1,000 supported updates per second in current systems.
1. INTRODUCTION: The paper develops an optimized online merge algorithm for dictionary-encoded in-memory column stores.Its stated goal is supporting enterprise application update performance on read-optimized databases.
1. INTRODUCTION: 30× speedup over unoptimized serial code is achieved by the proposed multi-core-aware merge optimizations.The design accounts for CPU caches and thread-level parallelism.

CHARACTERISTICS

Enterprise workloads combine substantial read activity with ongoing updates, motivating read-optimized systems that can support transactional and analytical processing together. Analyses of customer systems characterize workload, table-size, and value-domain properties used to guide the merge design.

CHARACTERISTICS: Mixed applications combine small transactional operations with complex reads over large data sets, while separate systems add latency to analytics.The paper uses these workloads to motivate combining transactional and analytical processing.
CHARACTERISTICS: More than 80% of customer-system queries are reads, while updates comprise about 17% of OLTP and 7% of OLAP queries.Measured update rates range from 3,000 to 18,000 updates per second.
CHARACTERISTICS: Only a limited number of the 73,979 analyzed tables contain many rows, making active large tables the main merge-scheduling concern.Smaller tables are easier to schedule because they are smaller and updated less often.
CHARACTERISTICS: Across more than 32 billion records, enterprise columns commonly use limited value domains, especially in financial accounting and inventory management.This behavior informs dictionary-size estimates and the suitability of dictionary encoding.
CHARACTERISTICS: The 144 largest tables range from 10 million to 1.6 billion rows, with an average of 65 million rows and 70 columns.A measured 33-million-row table required 12 minutes to merge 750,000 new rows in the initial implementation.

3. SYSTEM OVERVIEW

HYRISE combines compressed read-optimized main partitions with uncompressed write-optimized delta partitions to support mixed workloads. Periodic, transactionally safe merges control delta size while preserving efficient reads, but the design trades additional compression for update and merge performance.

Storage Layout: HYRISE stores each attribute in a compressed main partition and an uncompressed delta partition, with a CSB+ tree supporting delta insertions and sorted reads.The main partition uses dictionary compression, while the delta partition accumulates updates without compression.
Storage Layout: The delta partition must remain small because its uncompressed values increase memory consumption and can slow reads.Keeping it small motivates periodic merging.
Merge Process: HYRISE periodically merges main and delta partitions by building a replacement main partition and committing it atomically.Incoming updates use a temporary second delta during the merge, and locking is limited to short periods at the beginning and end.
Update Model: HYRISE models modifications as inserts and invalidations, preserving insertion order and implicit tuple offsets across attributes.The prototype uses dictionary encoding and bit compression because memory bandwidth limits the parallelized merge algorithm.
Update Model: The system avoids compression techniques that modify tuple order, trading stronger compression for simpler transaction handling, faster updates and merges, and retained change history.Run-length encoding is therefore not applied in the prototype.

4. UPDATE PERFORMANCE

Update performance depends on balancing delta-partition size against merge frequency and read overhead. The system represents updates with a main/delta layout whose merge reconstructs the dictionary and compressed values.

Update Performance: Update rate combines delta-update time and merge time, with targets of 3,000 and 18,000 updates/second.The paper defines TU as the time for ND delta updates and TM as the time for merging all table columns.
Delta-Partition Sizing: Small delta partitions speed inserts and limit read overhead but require more frequent merges, whereas large partitions reduce merge frequency but slow reads.Uncompressed delta values consume more compute resources and memory bandwidth, and comparisons can force dictionary materialization.
Delta-Partition Sizing: The system triggers a merge when delta tuples exceed a predefined fraction of main-partition tuples.This threshold controls the trade-off between delta growth and merge frequency.
Merge Example: During merging, main and delta values are concatenated into a new main column, a new dictionary is created, and tuple encodings are updated.The example increases the dictionary from 6 to 9 unique values, requiring 4 bits instead of 3 for each compressed value.

5. EFFICIENT MERGING ALGORITHM

The paper replaces dictionary searches in compressed-value updates with auxiliary translation structures, then parallelizes and optimizes the merge for modern CPU architectures. The resulting update path has linear-time components rather than search-dominated complexity.

Architecture-Aware Optimization: The algorithm uses architecture-aware optimizations and parallelization to exploit CPU compute and memory-bandwidth resources.Delta values are converted to fixed-width dictionary indices to improve cache-line use and enable SSE optimizations.
Algorithm Overview: The optimized merge combines main and delta partitions, updates the dictionary and compressed tuples, and creates an empty delta partition.For column j, inputs are Mj, Dj and UjM, while outputs are M′j and U′jM.
Dictionary Merging: The merge first extracts sorted unique delta values and linearly merges them with the main dictionary to form a duplicate-free dictionary.The dictionary merge uses two iterators that advance through the sorted inputs.
Compressed-Value Updates: The original compressed-value update step searches the updated dictionary for each main and delta value, making the search-dominated algorithm prohibitively slow.Binary search is used for both partitions in the baseline procedure.
Initial Performance Improvements: The auxiliary structure provides constant-cost translation during compressed-value updates, replacing lookup and binary search and reducing runtime to O(NM + ND).The new structure maps old compressed values to their positions in the merged dictionary.
Complexity: The optimized update step has runtime linear in the total number of tuples, significantly improving over the earlier formulation.The paper identifies Step 2(b) as the dominant cost in the original algorithm and replaces its search with linear-time processing.

6. ARCHITECTURE-AWARE MERGE IMPLEMENTATION

The merge implementation models compute and memory traffic, then exploits cache-aware processing and multiple CPU threads to accelerate dictionary and partition merging. Its parallelization balances work across threads and closely matches predicted compute- or bandwidth-limited performance.

Architecture-aware performance: Cache-friendly CSB+ tree traversal extracts delta-partition unique values while adapting node capacity to uncompressed value size.For 16-byte values, each cache-line-sized node holds at most three values.
Analytical model: The algorithm computes dictionary and partition memory traffic explicitly, including sequential scans, random auxiliary-structure accesses, and output writes.The model accounts for dictionary construction, tuple updates, auxiliary structures, and concatenated output columns.
Architecture-aware performance: The implementation’s measured performance closely matches the lower of compute- and bandwidth-based model bounds.This supports the model’s prediction that available processor resources constrain performance.
Parallelization: The parallel design uses task queues for columns and evenly divides tuple updates, improving load balance when column costs differ.For few-column tables, tuple-level parallelization is preferred; with tens to hundreds of columns, both schemes scale similarly on current CPUs.
Parallelization: Dictionary merging partitions sorted inputs into thread quantiles, locally removes duplicates, and synchronizes threads with a barrier after the first phase.Each thread records its unique-output count after merging its assigned ranges.

7. PERFORMANCE EVALUATION

The evaluation shows that architecture-aware parallel merge algorithms substantially reduce update costs and scale across CPU sockets, while cache residency and value uniqueness shape performance.

7.1 Impact of Delta Partition Size: 9–10 times: optimized Step 2 reduces merge time versus the unoptimized algorithm, leaving delta updates at 30%–55% of total time as delta size grows.The optimized design makes merge overhead a relatively small part of update runtime.
7.2 Impact of Value-Length and Percentage of Unique Values: 1.0 cycles per tuple: Step 2 approaches the bandwidth bound for 1% unique values because its gathered auxiliary structures fit in cache.For 100% unique values, all data structures must be accessed from memory, making Steps 1 and 2 bandwidth bound.
Parallel Scalability: 1.8–2.0 times: the implementation achieves near-linear scaling when expanding from one socket to two sockets across algorithm phases.This matches the approximately twofold increase in peak computing resources.
Parallel Scalability: 5 times: delta-partition updates scale across six threads, while parallel Step 1 reaches 4.3 times for 1% unique values because its three-phase algorithm performs extra comparisons.Step 2 for 1% unique values is memory-bandwidth bound; simultaneous multithreading does not improve performance because implementations are compute- or bandwidth-bound.
7.3 Impact of Main Partition Size and Percentage of Unique Entries: 81,000+ updates/second occur when auxiliary structures fit in cache, versus about 7,100 updates/second when memory bandwidth becomes limiting.The cache-sensitive result corresponds to auxiliary structures ranging from about 1 million to 10 million entries in the example discussed.
7.3 Impact of Main Partition Size and Percentage of Unique Entries: 7,100 updates/second remains stable when auxiliary structures do not fit cache, exceeding the 3,000-updates/second low-rate target even for 1-billion-entry partitions.High-rate targets are met for tables of at most 100 million rows when unique values are below 1%, while low-rate targets are always met.

8. RELATED WORK

Related work established column stores and processor-optimized database primitives, but this paper connects such optimizations to characterized enterprise workloads and merge processing.

Column-oriented databases: Column-store systems such as MonetDB/X100, C-Store, and Sybase IQ use vertically and attribute-wise partitioned schemas for read-mostly analytical workloads.The decomposition storage model provided a foundation for multiple column-store implementations.
Processor-aware database optimization: Prior processor-oriented research accelerated primitives including search, scan, sort, join, and aggregation, but did not describe effects on real workloads.The paper contrasts this focus with its enterprise-workload characterization and corresponding design choices.
Position of this work: This work differs by starting from real enterprise workload characterizations while designing and evaluating an optimized merge process for mixed workloads.The related-work contrast links processor resources to the paper’s database update problem.

9. DISCUSSION AND FUTURE WORK

The discussion frames optimized merging as a way for in-memory column stores to serve mixed transactional and analytical workloads, while identifying resource-aware extensions for future work.

Discussion: Mixed workloads combine transactional writes and reads with complex analytical queries, motivating read-optimized in-memory column stores that support both requirements.The paper connects this setting to increasing demand for real-time analytics on transactional data.
Discussion: Real-time analytics can support transactional applications with analytical functionality and faster, more detailed reports directly on up-to-date transactional data.The discussion anticipates increasing analytical queries and full-table scans in the database workload.
Future Work: Future work includes richer scan and lookup models, alternative delta structures, adaptive merge scheduling, lower memory consumption, and horizontal partitioning.The proposed scheduler could adjust merge parallelization to current bandwidth and system load, while incremental attribute processing could reduce memory demands.

10. CONCLUSIONS

The paper presents a linear-time algorithm for updating compressed main storage during merges, achieving a 30× speedup over current implementations and supporting mixed transactional and analytical workloads.

30× speedup over current implementations resulted from the paper’s linear-time compressed-storage update algorithm.The improved update performance enables in-memory column stores to execute transactional enterprise workloads while retaining high read performance for mixed transactional and analytical queries.