Sequence Compression - Revision history

Wikiservice: Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference

2026-08-28T09:59:36Z

Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference

← Older revision		Revision as of 11:59, 28 August 2026
Line 1:		Line 1:
	~~One of the most interesting compression techniques on columnar storages is '''sequence compression'''~~. Sequence Compression ~~in In-Memory Database yields 99% memory savings and a total of 13%~~		<!-- Copyright (C) 2026 Carl-Philip Haensch -->
			<!-- SPDX-License-Identifier: GPL-3.0-or-later -->
			= Sequence Compression =

	A sequence is a ~~column of numbers where each distance between two neighbouring numbers is equal~~. ~~Example:~~		Arithmetic-sequence storage represents a run by its start, stride, and length. Values such as <code>1,2,3,4</code>, repeated constants, descending counters, and regular timestamps can therefore occupy much less space than fixed-width values. A break starts another run.

	* <code>1 2 3 4 5 6 7 8 9</code>		MemCP evaluates this representation automatically during shard rebuild; users do not select it as a SQL type. Irregular columns may be better represented by bit packing, sparse storage, or another numeric encoding. Batch reads reconstruct consecutive values without a per-row virtual call.
	* <code>3 3 3 3 3 3 3 3 3 3</code>
	* <code>10 20 30 40</code>
	* <code>8 7 6 5</code>

	~~A sequence can be described by its starting point, its stride as well as its length:~~		== Runs and random access ==

	* <code>(1,1,9)</code>		A column such as <code>1,2,3,4,6,7,8</code> forms two runs: start 1/stride 1 and start 6/stride 1. The physical representation records where each run begins together with its start and stride. To read record <code>i</code>, the decoder finds the latest run whose starting record ID is not greater than <code>i</code>, then calculates <code>start + offset × stride</code>. Consecutive batch reads can advance through runs without repeating a full lookup.
	* <code>~~(3,0,10)~~</code>
	* <code>~~(10,10,4)~~</code>
	* <code>~~(8,-1,4)~~</code>

	~~The longer the sequence~~, ~~the higher the compression ratio~~. ~~For a typical SQL engine workload with AUTO_INCREMENT IDs, this means that you~~ can ~~store 150~~,~~000 IDs by just using three numbers~~.		AUTO_INCREMENT values, regular timestamps, counters, and sorted matrix coordinates often contain long runs. Random identifiers and frequently broken sequences do not. Reordering rows may improve sequences but can harm other locality or index requirements, so physical measurement remains necessary.

	~~Whenever the sequence is interrupted~~, a ~~new sequence has to be described. This means the column~~		For example, a relational inference matrix

	<~~code~~>~~1 2 3 4 6 7 8~~</~~code~~>		<pre>AIInferenceMatrix(matrix_id INTEGER, column_no INTEGER,
			row_no INTEGER, value DOUBLE)</pre>

	~~will be encoded as~~		can obtain long sequences in <code>row_no</code>/<code>column_no</code> when stored in matrix order, while keeping values relationally addressable instead of hiding the matrix in one blob. Whether that order is desirable also depends on updates and query predicates.

	~~<code>(1,1,4)(6,1,3)</code>~~		== Historical evaluations ==

	~~which is nearly~~ the ~~same storage~~-~~wise as~~ the ~~uncompressed column~~.		The early OppelBI experiment reported up to 99% reduction for individual sequential integer columns and a total dataset change from 17 MiB to 15 MiB after enabling sequence storage (the original MySQL source was reported as 55 MiB). A TPC-H scale-factor-1 import reported only 7 MiB saved in a roughly 1.1 GiB dataset because its generated values formed fewer useful runs. These observations preserve the important contrast between regular application data and randomized benchmark data; neither experiment recorded enough current methodology to be a product guarantee.

	~~So the compression ratio is as bigger as the the column is regular~~. ~~Since we use bit compression for the stride~~, ~~we can use a heuristic that less than 30% of the values~~ are ~~allowed to trigger~~ a ~~sequence-restart~~.		Compression depends on ordering and run regularity. Old example ratios are historical observations, not guarantees. The persisted storage magic/version assignments are permanent: format changes require a new version or magic byte and old readers must remain available.

	~~== Tweaking the format for fast random access ==~~		See [[Integer Compression]], [[In-Memory Compression, Columnar Compression Techniques]], and [[Performance Measurement]].
	To efficiently read a sequence compressed column, we have to alter the format a little bit. Instead of recording <code>(start, stride, count)</code>, we will record <code>(recordId, start, stride)</code>.

	The value <code>count</code> is automatically derived from the difference between its successor recordId. But as you see, we won’t need it anyways. <code>recordId</code> is a unsigned integer counting seemlessly from 0 to array_size-1. Whenever we want to find a specific value, we can use the following algorithm:

	* Given <code>i</code> is the recordId we want to read out
	* Do a binary search through the array of sequences such that we get the lowest <code>x</code> with <code>sequence[x]~~.recordId <= i</code>~~
	* Calculate the result by <code>sequence[x]~~.start + (i - sequence~~[~~x].recordId) * sequence~~[~~x].stride</code>~~

	~~== Evaluation ==~~
	In our example with OppelBI data (mostly online shop statistics), we were able to compress some integer storages by 99% which yields an overall saving of 13% of storage (our 55MB MySQL data is compressed to 15MB rather than 17MB)

	~~For the TPC~~-~~H benchmark~~, ~~we achieved a saving of 7MB for the 1.1GB dataset (scale factor 1) which is only 0~~,~~8%. We attribute this to the randomness of TPC-H’s data. Real world ERP or shop data is much more regular~~ and ~~less string-heavvy than TPC-H’s benchmark data.~~

	~~== Optimized for AI workloads ==~~
	~~Especially AI workloads like this table:~~

	~~<code>AIInferenceMatrix(matrixId integer, column integer, row integer, value double)</code>~~

	can be sequence-compressed very efficiently if you keep the row and column values sorted. This also yields a matrix’s <code>value</code> column memory layout that exactly matches the internal representation of the matrix that can be directly passed to TensorFlow or similar AI libraries.

	~~This implies that AI workloads no longer have to be stored as stupid BLOBs but rather can get a full relational storage which means easier access for partial data.~~

	~~== Conclusion ==~~
	~~Sequence Compression is a powerful technique to further compress data in RAM. It reduces cache misses and thus fastens up random access to „boring“ data~~.

Carli: Created page with "One of the most interesting compression techniques on columnar storages is '''sequence compression'''. Sequence Compression in In-Memory Database yields 99% memory savings and a total of 13% A sequence is a column of numbers where each distance between two neighbouring numbers is equal. Example: * `1 2 3 4 5 6 7 8 9` * `3 3 3 3 3 3 3 3 3 3` * `10 20 30 40` * `8 7 6 5` A sequence can be described by its starting point, its st..."

2024-05-17T13:04:07Z

Created page with "One of the most interesting compression techniques on columnar storages is '''sequence compression'''. Sequence Compression in In-Memory Database yields 99% memory savings and a total of 13% A sequence is a column of numbers where each distance between two neighbouring numbers is equal. Example: * <code>1 2 3 4 5 6 7 8 9</code> * <code>3 3 3 3 3 3 3 3 3 3</code> * <code>10 20 30 40</code> * <code>8 7 6 5</code> A sequence can be described by its starting point, its st..."

New page

One of the most interesting compression techniques on columnar storages is '''sequence compression'''. Sequence Compression in In-Memory Database yields 99% memory savings and a total of 13%

A sequence is a column of numbers where each distance between two neighbouring numbers is equal. Example:

* <code>1 2 3 4 5 6 7 8 9</code>
* <code>3 3 3 3 3 3 3 3 3 3</code>
* <code>10 20 30 40</code>
* <code>8 7 6 5</code>

A sequence can be described by its starting point, its stride as well as its length:

* <code>(1,1,9)</code>
* <code>(3,0,10)</code>
* <code>(10,10,4)</code>
* <code>(8,-1,4)</code>

The longer the sequence, the higher the compression ratio. For a typical SQL engine workload with AUTO_INCREMENT IDs, this means that you can store 150,000 IDs by just using three numbers.

Whenever the sequence is interrupted, a new sequence has to be described. This means the column

<code>1 2 3 4 6 7 8</code>

will be encoded as

<code>(1,1,4)(6,1,3)</code>

which is nearly the same storage-wise as the uncompressed column.

So the compression ratio is as bigger as the the column is regular. Since we use bit compression for the stride, we can use a heuristic that less than 30% of the values are allowed to trigger a sequence-restart.

== Tweaking the format for fast random access ==
To efficiently read a sequence compressed column, we have to alter the format a little bit. Instead of recording <code>(start, stride, count)</code>, we will record <code>(recordId, start, stride)</code>.

The value <code>count</code> is automatically derived from the difference between its successor recordId. But as you see, we won’t need it anyways. <code>recordId</code> is a unsigned integer counting seemlessly from 0 to array_size-1. Whenever we want to find a specific value, we can use the following algorithm:

* Given <code>i</code> is the recordId we want to read out
* Do a binary search through the array of sequences such that we get the lowest <code>x</code> with <code>sequence[x].recordId <= i</code>
* Calculate the result by <code>sequence[x].start + (i - sequence[x].recordId) * sequence[x].stride</code>

== Evaluation ==
In our example with OppelBI data (mostly online shop statistics), we were able to compress some integer storages by 99% which yields an overall saving of 13% of storage (our 55MB MySQL data is compressed to 15MB rather than 17MB)

For the TPC-H benchmark, we achieved a saving of 7MB for the 1.1GB dataset (scale factor 1) which is only 0,8%. We attribute this to the randomness of TPC-H’s data. Real world ERP or shop data is much more regular and less string-heavvy than TPC-H’s benchmark data.

== Optimized for AI workloads ==
Especially AI workloads like this table:

<code>AIInferenceMatrix(matrixId integer, column integer, row integer, value double)</code>

can be sequence-compressed very efficiently if you keep the row and column values sorted. This also yields a matrix’s <code>value</code> column memory layout that exactly matches the internal representation of the matrix that can be directly passed to TensorFlow or similar AI libraries.

This implies that AI workloads no longer have to be stored as stupid BLOBs but rather can get a full relational storage which means easier access for partial data.

== Conclusion ==
Sequence Compression is a powerful technique to further compress data in RAM. It reduces cache misses and thus fastens up random access to „boring“ data.