In-Memory Compression, Columnar Compression Techniques: Difference between revisions
No edit summary |
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 --> | |||
= In-Memory Compression, Columnar Compression Techniques = | |||
MemCP stores each physical column in an encoding selected from its values and access pattern. Implementations include constants, bit-packed integers, exact decimals, floats, dictionaries and low-cardinality entropy coding, shared string prefixes, sparse/default storage, arithmetic sequences, blobs, and index-oriented representations. | |||
The goal is to reduce cache lines and memory bandwidth while preserving sequential batch access. Scan paths prefer range and multi-record reads so decoding occurs per batch rather than through one function call per value. Recent writes and deletes live in shard delta structures until rebuild folds them into a newly selected main representation. | |||
== Why compressed data can execute faster == | |||
CPU arithmetic is often cheaper than waiting for another cache line. A three- or five-bit packed value needs decoding, but many more values fit in L1/L2/L3 cache and memory transfers. Column layout compounds the effect by avoiding unrelated attributes. Compression helps most when decoding is simple and scans are sequential; it may help less for unpredictable random access or already incompressible values. | |||
Modern cores can retire many arithmetic instructions while waiting for DRAM. L1 is tiny and fast, later caches are larger and slower, and main-memory bandwidth is shared between cores. Compact sequential columns increase the useful values per cache line and let hardware prefetchers work. This is why MemCP treats lightweight compression as an execution technique, not merely a disk-space feature. | |||
Modern | |||
The aspiration is that compressed scans remain fast beyond the bandwidth point where wider row representations stop scaling. Whether a concrete query achieves that depends on decoder, selected columns, data distribution, JIT/vectorization coverage, NUMA placement and concurrent traffic. | |||
== Selection during rebuild == | |||
MemCP analyzes a physical shard column, compares applicable representations, and builds the chosen encoding in a second pass. The choice is local to the observed values rather than a permanent SQL type decision. Delta storage remains write-friendly until a rebuild incorporates it, so users can update a compressed table without rewriting its entire main column per row. | |||
Useful signals include minimum/maximum and integer width, distinct values and frequencies, shared string prefixes, default/NULL density, monotonic or arithmetic runs, and whether an index-oriented ordering is valuable. | |||
== Reading and measuring == | |||
Late materialization asks only referenced columns to decode. Batch range and multi-record operations avoid virtual calls in the inner row loop, and operators can consume compact identifiers or boundaries before materializing user-visible values. | |||
Compression ratios depend on type, value range, cardinality, ordering, null density, and workload; historical measurements are not product guarantees. Reloadable persistent columns and indexes may be evicted from RAM, while memory-engine rows may not. | |||
Persisted encodings follow a permanent magic-byte and version contract. A changed binary layout must introduce a new version or magic byte while retaining readers for all earlier formats. | |||
== | == Historical cache experiment == | ||
An early experiment loaded 10,000 rows (reported around 3 MiB) on an AMD Ryzen 9 3900X with 32 GiB RAM, searched an unindexed postcode column and printed the one matching row. The same Scheme scan was repeated before and after rebuilding delta data into compressed main storage. | |||
{| class="wikitable" | |||
! Representation !! Recorded timings | |||
|- | |||
| Row-oriented delta state || 3.928691, 3.920911, 4.212188, 5.900366, 7.190586, 7.197987, 7.210748, 7.164205, 7.161525, 7.324479, 7.342900 and 7.338970 ms | |||
|- | |||
| Compressed main columns || 3.891690, 3.899201, 3.876729, 5.599179, 6.890489, 6.774777, 6.896110, 6.770937, 6.783257, 6.786928, 6.798617 and 6.780997 ms | |||
|} | |||
The original interpretation attributed the later plateau partly to garbage-collector activity and described roughly a 7% steady-state improvement alongside a large memory reduction. The experiment did not record a current commit, statistical treatment, isolation from printing/GC or independent repetitions. Its raw samples are retained because they motivate the cache-locality design; they must be rerun with the current framework before supporting a product comparison. | |||
See [[Columnar Storage]], [[Integer Compression]], [[Dictionary Compression]], [[Sequence Compression]], [[Index Compression]], and [[Memory Management and Eviction]]. | |||
Latest revision as of 11:59, 28 August 2026
In-Memory Compression, Columnar Compression Techniques
MemCP stores each physical column in an encoding selected from its values and access pattern. Implementations include constants, bit-packed integers, exact decimals, floats, dictionaries and low-cardinality entropy coding, shared string prefixes, sparse/default storage, arithmetic sequences, blobs, and index-oriented representations.
The goal is to reduce cache lines and memory bandwidth while preserving sequential batch access. Scan paths prefer range and multi-record reads so decoding occurs per batch rather than through one function call per value. Recent writes and deletes live in shard delta structures until rebuild folds them into a newly selected main representation.
Why compressed data can execute faster
CPU arithmetic is often cheaper than waiting for another cache line. A three- or five-bit packed value needs decoding, but many more values fit in L1/L2/L3 cache and memory transfers. Column layout compounds the effect by avoiding unrelated attributes. Compression helps most when decoding is simple and scans are sequential; it may help less for unpredictable random access or already incompressible values.
Modern cores can retire many arithmetic instructions while waiting for DRAM. L1 is tiny and fast, later caches are larger and slower, and main-memory bandwidth is shared between cores. Compact sequential columns increase the useful values per cache line and let hardware prefetchers work. This is why MemCP treats lightweight compression as an execution technique, not merely a disk-space feature.
The aspiration is that compressed scans remain fast beyond the bandwidth point where wider row representations stop scaling. Whether a concrete query achieves that depends on decoder, selected columns, data distribution, JIT/vectorization coverage, NUMA placement and concurrent traffic.
Selection during rebuild
MemCP analyzes a physical shard column, compares applicable representations, and builds the chosen encoding in a second pass. The choice is local to the observed values rather than a permanent SQL type decision. Delta storage remains write-friendly until a rebuild incorporates it, so users can update a compressed table without rewriting its entire main column per row.
Useful signals include minimum/maximum and integer width, distinct values and frequencies, shared string prefixes, default/NULL density, monotonic or arithmetic runs, and whether an index-oriented ordering is valuable.
Reading and measuring
Late materialization asks only referenced columns to decode. Batch range and multi-record operations avoid virtual calls in the inner row loop, and operators can consume compact identifiers or boundaries before materializing user-visible values.
Compression ratios depend on type, value range, cardinality, ordering, null density, and workload; historical measurements are not product guarantees. Reloadable persistent columns and indexes may be evicted from RAM, while memory-engine rows may not.
Persisted encodings follow a permanent magic-byte and version contract. A changed binary layout must introduce a new version or magic byte while retaining readers for all earlier formats.
Historical cache experiment
An early experiment loaded 10,000 rows (reported around 3 MiB) on an AMD Ryzen 9 3900X with 32 GiB RAM, searched an unindexed postcode column and printed the one matching row. The same Scheme scan was repeated before and after rebuilding delta data into compressed main storage.
| Representation | Recorded timings |
|---|---|
| Row-oriented delta state | 3.928691, 3.920911, 4.212188, 5.900366, 7.190586, 7.197987, 7.210748, 7.164205, 7.161525, 7.324479, 7.342900 and 7.338970 ms |
| Compressed main columns | 3.891690, 3.899201, 3.876729, 5.599179, 6.890489, 6.774777, 6.896110, 6.770937, 6.783257, 6.786928, 6.798617 and 6.780997 ms |
The original interpretation attributed the later plateau partly to garbage-collector activity and described roughly a 7% steady-state improvement alongside a large memory reduction. The experiment did not record a current commit, statistical treatment, isolation from printing/GC or independent repetitions. Its raw samples are retained because they motivate the cache-locality design; they must be rerun with the current framework before supporting a product comparison.
See Columnar Storage, Integer Compression, Dictionary Compression, Sequence Compression, Index Compression, and Memory Management and Eviction.