Alibaba just cut 70% off database index bloat. The trick is in the prefixes.

For database operators, secondary indexes are a double-edged sword. They accelerate queries but can easily consume more storage than the primary table. In SaaS multi-tenant systems, e-commerce platforms, and distributed tracing stores, indexes often account for over half of total instance storage. That bloat drives up costs, eats into buffer pool efficiency, amplifies IOPS pressure, and increases B+ tree contention, as Alibaba's broader cloud strategy continues to push for infrastructure-level optimizations.

Alibaba Cloud's PolarDB-X team has published a detailed technical account of a new compression scheme called Secondary Prefix Compression (SPC), implemented in the storage engine's data node. Instead of applying general-purpose compression at the block level, as InnoDB's built-in table compression and transparent page compression do, SPC exploits structural redundancy in secondary index B+ tree leaf pages. The result is a lightweight, page-local prefix dictionary that shrinks index space by 30% to 70% while keeping CPU overhead under control. This approach parallels how quantization frameworks like Unsloth exploit model-level redundancy to achieve dramatic size reductions with minimal quality loss.

The anatomy of index bloat

In InnoDB, each secondary index stores a tuple of the secondary key (SK) and the primary key (PK). Because indexes are sorted by SK, adjacent records within a leaf page tend to share long common prefixes. Fields such as order IDs, SKUs, URLs, file paths, and trace IDs exhibit heavy prefix similarity in production workloads. But under InnoDB's stock COMPACT record format, every record stores its full SK independently, even consecutive records with the same SK, where only the trailing PK differs.

This is functionally correct but spatially wasteful. The redundancy lowers leaf-page space utilization, which dilutes buffer pool hot-data coverage, increases page access frequency, and raises the rate of B+ tree splits and SX-latch contention. General-purpose block compressors like zlib or lz4 can address the symptom, but their decompression cost on every read and the dual in-memory page copies under table compression make them a poor fit for OLTP workloads that demand low-latency access. Similar architectural trade-offs have surfaced in other domains, such as cloud GPU workload scheduling, where the overhead of data movement can dwarf compute costs.

SPC: per-page prefix dictionaries

SPC takes a different route. At the heart of the scheme is a per-page dictionary of common prefixes, maintained as a small metadata area within each 16 KB index page. Each record stores only a dictionary reference, a length indicating how many bytes of that prefix it shares, and its own remaining suffix. The logical value and sort order of the record stay unchanged, but repeated prefixes get stored only once per page.

The table below compares SPC with existing MySQL InnoDB compression options across key dimensions:

The choice of a per-page shared dictionary, as opposed to per-record delta prefixes or a cross-page shared dictionary, is a deliberate engineering trade-off. The PolarDB-X team evaluated all three approaches and concluded that the per-page design achieves the best balance: compression scope is strictly confined to a single page, avoiding global metadata management and cascading write amplification, while still capturing the dominant source of redundancy, adjacent-record prefix similarity.

Split-triggered encoding and the Slice abstraction

One of SPC's most pragmatic design decisions is when to encode. The team adopted a split-triggered strategy: records are inserted in their uncompressed form. Only when a page is about to run out of space and trigger a B+ tree split does SPC encode the entire page. That means cold or sparsely filled pages never incur encoding overhead, and the cost gets amortized over the hundreds or thousands of DML operations that fill a page. Moreover, the space freed by compression often lets an insert that would have caused a split complete in place, compression itself acts as split-mitigation relief.

The encoding algorithm itself is a three-phase greedy approximation that runs in linear time. It scans the sorted records on the page, partitions them into candidate prefix intervals based on common prefix lengths, and then applies a merge heuristic to balance dictionary size against net byte savings. The dictionary is capped at 128 entries, and records whose prefix is too short or not covered retain their original form, compressed and uncompressed records coexist on the same page. This lazy-encoding approach mirrors the philosophy behind recent RL training optimizations that defer expensive operations until their cost can be amortized across a large batch of work.

On the read path, SPC introduces a Slice abstraction in InnoDB's record management layer. For standard COMPACT records, Slice degenerates to a direct pointer access identical to upstream behavior. For SPC records, it lazily assembles the dictionary prefix and record suffix into a contiguous memory region on demand. Critically, the abstraction also supports partial decompression: when comparing an SPC record against a query tuple, the comparison can be performed column by column directly in compressed form, using the dictionary entry and extended offsets, without first reconstructing a full uncompressed record. That eliminates one memcpy and one temporary allocation on the hot read path.

The Slice layer ensures that SPC is semantically opaque to the rest of InnoDB, all upstream code paths (MVCC, undo, purge, locking, change buffer, replication, backup/restore) continue to work unchanged. From the outside, SPC is purely a physical, in-page storage optimization.

Benchmark results: up to 47% throughput gains under I/O pressure

The PolarDB-X team ran a series of sysbench benchmarks using a table schema designed to simulate typical prefix-repetition characteristics: 3 INT columns with low cardinality, 6 VARCHAR(64) columns with a 40-byte common prefix, and 12 secondary indexes. With SPC off, a single table of 1 million rows occupied 1.8 GB, of which secondary indexes consumed 1.16 GB. With SPC on, the table shrank to 1.1 GB, with secondary indexes at 0.52 GB, a 55% compression on secondary indexes and 38% overall.

The most striking results came under I/O-bound conditions with a 4 GB buffer pool (covering roughly 30% of the dataset without SPC):

With an 8 GB buffer pool, doubling the coverage to nearly 50%, the improvements in read-IO-bound workloads jumped to +46.8% for read_only and +47.5% for read_write. The write_only workload remained virtually flat (+1.6%) because its read path locates rows by primary key and never traverses secondary index pages, while the split-triggered encoding ensures routine DML doesn't incur encoding overhead. These results echo a pattern seen in specialized AI models: targeted, domain-specific optimizations often outperform general-purpose approaches on their home turf.

With the buffer pool set to 32 GB, large enough for the entire dataset to reside in memory, the I/O advantage disappeared. Differences across all three workloads fell within ±2.4%, confirming that SPC's decompression overhead on the pure CPU path is minimal, and its write impact is negligible.

How it compares with other databases

Among major database systems, Microsoft SQL Server's page compression is closest in spirit to SPC: it applies a three-layer pipeline of row compression, prefix compression, and dictionary compression, triggered when a page fills up. PostgreSQL's B-tree deduplication consolidates duplicate keys but does not handle partial prefix sharing. Oracle's Advanced Index Compression uses adaptive per-block compression, while its basic prefix compression (COMPRESS n) operates at the column level. SPC's byte-level precision gives it finer granularity than Oracle's column-level approach, and its confinement to secondary indexes, where redundancy is highest, makes it a targeted optimization rather than a one-size-fits-all compressor. The same principle of narrowing the scope of a heavy operation applies in neuromorphic chip design, where specialized architectures can dramatically outperform general-purpose processors on specific workloads.

Bottom line

SPC is not a radical departure from existing database compression techniques, but it is a well-executed, practical optimization that addresses a specific pain point: secondary index bloat in OLTP workloads. By restricting compression to per-page prefix dictionaries triggered only at page-split time, the PolarDB-X team has managed to reduce index storage by 30% to 70% while keeping the CPU and complexity costs low enough for production deployment. For cloud operators already running MySQL-compatible workloads on Alibaba Cloud's PolarDB-X, SPC offers a meaningful lever for cutting storage bills and improving I/O-bound query performance, without application changes.

For the broader database engineering community, the lesson is that structural redundancy in sorted B+ tree pages is a rich vein worth mining, and that a lightweight, tightly scoped approach can outperform heavyweight general-purpose compressors in the OLTP sweet spot. The full technical details are available in the PolarDB-X team's blog post.