File formats

WiredTiger supports two underlying file formats: row-store and column-store, both are key/value stores.

In a row-store, both keys and data are variable-length byte strings. In a column-store, keys are 64-bit record numbers (format type 'r'), and data items are either variable- or fixed-length byte strings.

Generally, row-stores are faster for queries where all of the columns are required by every lookup (because there's only a single set of meta-data pages to read into the cache and search). Column-stores are faster when most queries require only a subset of the columns (because columns can be separated into multiple files and only the columns being returned need be present in the cache).

Row-store keys and values, and variable-length column-store values, can be up to (4GB - 512B) in length. Keys and values too large to fit on a normal page are stored as overflow items in the file, and are likely to require additional file I/O to access.

Fixed-length column-store values (format type 't'), are limited to 8-bits, and only values between 0 and 255 may be stored. Additionally, there is no out-of-band fixed-length "deleted" value, and deleting a value is the same as storing a value of 0. For the same reason, storing a value of 0 will cause cursor scans to skip the record.

WiredTiger does not support duplicate data items: there can be only a single value for any given key, and applications are responsible for creating unique key/value pairs.

WiredTiger allocates space from the underlying files in block units. The minimum file allocation unit WiredTiger supports is 512B and the maximum file allocation unit is 512MB. File block offsets are 64-bit (meaning the maximum file size is very, very large).

File formats and compression

Row-stores support four types of compression: prefix compression, dictionary compression, Huffman encoding and stream compression.

Prefix compression reduces the size requirement of both in-memory and on-disk objects by storing any identical key prefix only once per page. The cost is minor additional CPU memory use when searching the in-memory tree and when writing pages to disk.

Dictionary compression reduces the size requirement of both the in-memory and on-disk objects by storing any identical value only once per page. The cost is minor additional CPU and memory use when returning values from the in-memory tree and when writing pages to disk. Note that dictionary compression in WiredTiger is intended for relatively small dictionaries of unique values; configuring dictionaries of tens of thousands of values might result in a higher CPU cost.

Huffman encoding reduces the size requirement of both the in-memory and on-disk objects by compressing individual key/value items, and can be separately configured either or both keys and values. The cost is additional CPU and memory use when searching the in-memory tree (if keys are encoded), and additional CPU and memory use when returning values from the in-memory tree and when writing pages to disk. Note the additional CPU cost of Huffman encoding can be high, and should be considered. (See Huffman Encoding for details)

Stream compression reduces the size requirement of on-disk objects by compressing blocks of the backing object's file. The cost is additional CPU and memory use when reading and writing pages to disk. Note the additional CPU cost of stream compression can be high, and should be considered. (See Compressors for details).

Column-stores with variable-length byte string values support three types of compression: run-length encoding, Huffman encoding and block stream compression.

Run-length encoding reduces the size requirement of both the in-memory and on-disk objects by storing sequential, duplicate values in the store only a single time (with an associated count). The cost is minor additional CPU and memory use when returning values from the in-memory tree and when writing pages to disk.

Huffman encoding reduces the size requirement of both the in-memory and on-disk objects by compressing individual value items. The cost is additional CPU and memory use when returning values from the in-memory tree and when writing pages to disk. Note the additional CPU cost of Huffman encoding can be high, and should be considered. (See Huffman Encoding for details)

Stream compression reduces the size requirement of on-disk objects by compressing blocks of the backing object's file. The cost is additional CPU and memory use when reading and writing pages to disk. Note the additional CPU cost of stream compression can be high, and should be considered. (See Compressors for details).

Column-stores with fixed-length byte values support a single type of compression: stream compression.

Stream compression reduces the size requirement of on-disk objects by compressing blocks of the backing object's file. The cost is additional CPU and memory use when reading and writing pages to disk. Note the additional CPU cost of stream compression can be high, and should be considered. (See Compressors for details).