Motivation

Compression is used extensively by all database vendors to reduce TCO and improve performance. Compression could be applied to different parts of the system to achieve the following goals:

• Less writes to disk - less IO call, less disk space needed
• Less reads from disk - less IO call, less RAM is needed to accommodate the same number of records.

Performance numbers of other vendors demonstrate that we could expect 2x-4x decrease in required disk space and >1.5x increase in throughput (ops/sec) on typical workloads.

Competitive analysis

This section describes general compression approaches and their pros and cons. The following compression mechanisms are implemented in practice:

1. Data format 
2. Index prefix compression
3. Page-level compression
4. WAL compression
5. Per-column compression
6. Compression on file system level
7. Column store

Data Format

Efficient disk usage starts with proper data layout. Vendors strive to place data in pages in such a way that total overhead is kept as low as possible while still maintaining high read speed. Typically this is achieved as follows:

1. Common metadata such is stored outside of data page
2. Numeric types are written using varlen encoding (e.g. int data type may take 1-5 bytes instead of 4)
3. Fixed-length string data types (CHAR, NCHAR) are trimmed
4. NULL and zero values are optimized to consume no space, typically with special bitmap (e.g. if there are 

Examples:

1. SQL Server row format [1] - varlen, CHAR trimming, NULL/zero optimization
2. MySQL row format [2] - no varlen, no CHAR trimming, NULL/zero optimization

[1] https://docs.microsoft.com/en-us/sql/relational-databases/data-compression/row-compression-implementation?view=sql-server-2017
[2] https://dev.mysql.com/doc/refman/5.6/en/innodb-physical-record.html

Index Prefix Compression

Secondary indexes tend to have entries with common prefix. E.g. {'IndexedValue', link1}, {'indexedValue', link2}. Prefix compression technique extracts common prefixes from entries on the index page and place them in a special directory within a page.

Prefix compression could be applied to the following index types:

1. Non-unique single column secondary index
2. Non-unique and unique multi-column secondary index

Prefix compression could be implemented as follows:

1. Static - compression is applied to all index rows irrespective of whether it is beneficial or not. Attributes with low cardinality are compressed well. Contrary, attributes with high cardinality may have negative compression rates. Decision whether to compress or not is delegated to user (typically DBA)
2. Dynamic - compression is either applied or not applied to indexed values on page-by-page basis based on some internal heuristics. Negative compression rates are avoided automatically, but implementation is more complex.

Examples:

1. Oracle index compression (static) [1]
2. Oracle advanced index compression (dynamic) [2]
3. MongoDB index compression [3]

[1] https://blogs.oracle.com/dbstorage/compressing-your-indexes:-index-key-compression-part-1

[2] https://blogs.oracle.com/dbstorage/compressing-your-indexes:-advanced-index-compression-part-2

[3] https://docs.mongodb.com/manual/core/wiredtiger/#storage-wiredtiger-compression

Page-level Compression

The whole pages could be compressed. This gives 2x-4x reduciton in size on average. Two different approaches are used in practice - without in-memory compression, with in-memory compression

Without in-memory compression

Data is stored in-memory as is, in uncompressed form. When it is time to flush data to disk compression is applied. If data size is reduced significantly, data is stored in compressed form. Otherwise it is stored in plain form (compression faiure). Big block sizes (e.g. 32Kb) is typically used in this case to achieve higher compression rates. Data is still being written to disk in blocks of smaller sizes. E.g. one may have 32Kb block in-memory, which is compressed to 7Kb, which is then written as two 4Kb blocks to disk. Vendors allow to select compression algorithm (Snappy, zlib, lz4, etc.).

Hole punching with fallocate [1] might be added if underlying file system supports it. In this case compressed block is written as is, but then empty space is trimmed with separate system call. E.g. if 32Kb block is compressed to 6.5Kb, then 32Kb is written as is, and then 32 - 7 = 25 Kb are released. 

Advantages:

• High compression rates
• No overhead when reading data from memory
• Ability to choose compression algorithm

Disadvantages:

• High RAM usage
• Need to re-compress data frequently
• Hole-punching is supported by very few file systems (XFS, ext4, Btrfs), and may lead to heavy file maintenance [2]

Examples:

1. MySQL Table Compression - uses different in-memory and disk block sizes, block data is fully re-compressed on every access [3]
2. MySQL Page Compression - uses hole-punching instead [4]
3. MongoDB with Snappy codec - gathers up to 32Kb of data and then try to compress it [5]5

[1] http://man7.org/linux/man-pages/man2/fallocate.2.html

[2] https://mariadb.org/innodb-holepunch-compression-vs-the-filesystem-in-mariadb-10-1/

[3] https://dev.mysql.com/doc/refman/5.7/en/innodb-compression-background.html

[4] https://mysqlserverteam.com/innodb-transparent-page-compression/

[5] https://www.objectrocket.com/blog/company/mongodb-3-0-wiredtiger-compression-and-performance/

Draft materials

Motivation

TBD

Proposed changes

TBD

Tickets