Sequence Compression: Difference between revisions
(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...") |
Wikiservice (talk | contribs) (Refresh MemCP documentation: accuracy, operational guidance, performance profile and maintained API reference) |
||
| Line 1: | Line 1: | ||
<!-- Copyright (C) 2026 Carl-Philip Haensch --> | |||
<!-- SPDX-License-Identifier: GPL-3.0-or-later --> | |||
= Sequence Compression = | |||
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. | |||
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. | |||
== Runs and random access == | |||
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. | |||
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. | |||
For example, a relational inference matrix | |||
< | <pre>AIInferenceMatrix(matrix_id INTEGER, column_no INTEGER, | ||
row_no INTEGER, value DOUBLE)</pre> | |||
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. | |||
== Historical evaluations == | |||
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. | |||
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. | |||
See [[Integer Compression]], [[In-Memory Compression, Columnar Compression Techniques]], and [[Performance Measurement]]. | |||
In | |||
Latest revision as of 11:59, 28 August 2026
Sequence Compression
Arithmetic-sequence storage represents a run by its start, stride, and length. Values such as 1,2,3,4, repeated constants, descending counters, and regular timestamps can therefore occupy much less space than fixed-width values. A break starts another run.
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.
Runs and random access
A column such as 1,2,3,4,6,7,8 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 i, the decoder finds the latest run whose starting record ID is not greater than i, then calculates start + offset × stride. Consecutive batch reads can advance through runs without repeating a full lookup.
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.
For example, a relational inference matrix
AIInferenceMatrix(matrix_id INTEGER, column_no INTEGER,
row_no INTEGER, value DOUBLE)
can obtain long sequences in row_no/column_no 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.
Historical evaluations
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.
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.
See Integer Compression, In-Memory Compression, Columnar Compression Techniques, and Performance Measurement.