Integer Compression - Revision history

Carli: /* See also */

2024-05-18T11:58:33Z

Carli at 20:51, 17 May 2024

2024-05-17T20:51:26Z

@@ Line 21: / Line 21: @@
 Besides the memory savings, this compression can lead to massive speedups due in scenarios where memory bandwith or latency is a bottleneck.
 == See also ==
 https://github.com/lemire/FastPFor

Carli: Created page with "Traditional Database Management Systems use fixed width integers of 32 or 64 bit that are administered by the database operator. MemCP however uses a different approach: according to a data analysis pass, we detect the maximum bit width of an integer to be encoded into our database. This is done by: * finding the smallest integer in a shard * finding the highest integer * `offset = smallest` * `bitwidth = ⌈ld (highest - smallest)⌉` * allocate..."

2024-05-17T20:43:30Z

Created page with "Traditional Database Management Systems use fixed width integers of 32 or 64 bit that are administered by the database operator. MemCP however uses a different approach: according to a data analysis pass, we detect the maximum bit width of an integer to be encoded into our database. This is done by: * finding the smallest integer in a shard * finding the highest integer * <code>offset = smallest</code> * <code>bitwidth = ⌈ld (highest - smallest)⌉</code> * allocate..."

New page

Traditional Database Management Systems use fixed width integers of 32 or 64 bit that are administered by the database operator.

MemCP however uses a different approach: according to a data analysis pass, we detect the maximum bit width of an integer to be encoded into our database.

This is done by:

* finding the smallest integer in a shard
* finding the highest integer
* <code>offset = smallest</code>
* <code>bitwidth = ⌈ld (highest - smallest)⌉</code>
* allocate <code>⌈(num_items * bitwidth) / 64⌉</code> 64-bit integers
* the values are stored at the position <code>item_id * bitwidth</code> inside that memory blob

The analysis and compression is done in the [[Columnar Storage|ColumnStorage]] interface.

Integer compression can lead to extensive memory savings:

* Binary values use up 1 bit instead of 8 bits or 32 bits per value
* through the offset handling, unix timestamps can be encoded in 23 bits instead of 32 bits
* IDs and other foreign keys can be encoded in <code>⌈ld highest_ID⌉</code> bits per item

Besides the memory savings, this compression can lead to massive speedups due in scenarios where memory bandwith or latency is a bottleneck.

== See also ==
https://github.com/lemire/FastPFor

← Older revision		Revision as of 13:58, 18 May 2024
Line 98:		Line 98:

	== See also ==		== See also ==
	https://github.com/lemire/FastPFor
			* https://github.com/lemire/FastPFor
			* https://wwwdb.inf.tu-dresden.de/wp-content/uploads/T_2014_Master_Patrick_Damme.pdf