How does data store compression speed up data warehouses?

Therefore, data compression must significantly slow down a database.

Which concludes a masterstroke in logical fallacy!

One of the essential reasons why compression can make things faster, is that the subsystem for durable storage is considerably slower and more serialised than the subsystem which consists of the central processing cores.

Durable storage is also usually not directly byte-addressable and random-access at that granularity, but consists of reading and writing whole blocks of sequential data to and from main memory.

Economising on the volume of raw data that is sent to and brought from storage under these conditions, can therefore improve performance more than avoiding modest amounts of processing upon the data entailed by a compression algorithm.

It's also important to recognise that database engines are not optimised for fastest retrieval of a random single data point, with the entire machinery starting and finishing at idle, but for throughput of data in bulk under sustained load where access patterns are usually far from random.

It is possible for a particular machine or algorithm to be slower at the first whilst being considerably faster at the second because it better facilitates concurrent/overlapping processing.

The benefit will depend on the type of access you are doing. If you only care about random access performance, compression will probably not help much. But other types of access patterns may see a much greater benefit.

You would typically compress data into blocks that can be individually decompressed, and add these blocks to an index so you can quickly find the block containing the required piece of data. Naturally there will be a tradeoff here between larger blocks, and therefore compression efficiency, and the amount of unneeded data that need to be decompressed. So the claim that compressed data cannot be indexed at all is clearly false. Just look at video compression, where seeking is more or less instant.

But the memory hierarchy also matters. IO costs tend to dominate, and reading sequential data tend to be much faster than random access, so the cost of reading more data than needed may not be that significant. Decompression can also be fairly cheap, lz4 claims 4970MB/s/core, and simple delta compression may be even cheaper.

In some cases, compression may allow the data to be stored on smaller but faster SSDs, or even in memory, greatly reducing the IO latency and improving performance.

If there is a pattern to queries, like fetching multiple related rows at the same time, then compression may reduce the amount of needed IO, and therefore help with overall performance. That is ofc assuming that the data can be compressed in the first place. I do not think anyone is claiming that compression is suitable for all kinds of data and use cases.

Data warehouse/analytical database systems are optimizing for aggregate reporting queries that touch many rows to generate their result set. Things like 'total sales for the xth quarter' or 'average time spent on the site of people who bought a baz widget'. These queries tend to have relatively large amounts of data per index key. As such you can benefit from compression without sacrificing indexing, by compressing on a per index key, or group of index keys. Then the index selects which compressed blobs the query needs, and the query processes the entire blob.

Let me first address the assertion that "Reads will necessarily require a decompression step." Some common aggregate expressions can be evaluated without decompression.

Say we have 1,000 rows which include a dollar-value column. For the sake of illustration we'll say the first 600 rows all are $5 and the others are $7.

Uncompressed, to get the total dollar value requires loading 1,000 values and 999 computations. Similarly a count requires touching 1,000 values. These are very common analytical expressions.

With run length encoding the column can be stored as [(600,$5),(400,$7)]. Total value can be calculated as ((600 * 5)+(400 * 7)) and count as (600+400). Many fewer values are loaded and calculations performed. Repeat this across the very many compressed blocks an OLAP system may hold and performance improvement can be noticeable.

Usually the system will capture summary information per block, per column, as it is compressed. Minimum, maximum, total, row count & null count are typical. Using this metadata, stored in the DBMS catalog, some results can be found without even reading table data.

Second, the assertion that "Fast datastore reads in a database come from ... the ability to selectively read only the relevant data in a random-access manner" is not true. Snowflake holds data internally in a columnar format. It does not allow for the creation of secondary indexes at all. It is widely held to be a capable OLAP system.

Further there are a class of DBMS built around GPUs. They (generally) forgo any indexing, instead relying on the device's large bandwidth and parallel processing to treat all access as a table scan. These have not gained wide popularity, but they exist.

Thirdly the assertion "Indexing into a compressed data store is impossible" is false. SQL Server, for one, permits clustered columnstore indexes (cci). "Clustered" means they constitute the on-disk sequencing of base table rows. As columnstores they are compressed. Secondary BTree indexes can be defined on a table that is a cci.

Rows in a compressed block are still in some sequence. Each set of column values in the block are an array. Any compression on that array retains the original sequencing. A secondary index can, at its leaf level, hold a pointer to the block and offset within the block. Compression algorithm design makes it simple to return the ith value for each compressed column.

Compressed data is typically 20% the size of uncompressed. This means loading data takes one fifth as much time. The corollary being five times as much data can be retained in RAM ready to answer the next query, improving performance.

Having multiple column-values adjacent in memory facilitates movement en masse through the memory hierarchy and onto cores, where they are amenable to SIMD techniques. When a predicate eliminates rows this can be recorded in an related bitmap. Each predicate can be evaluated in parallel on separate cores and the bitmaps ANDed together at the end.

A new Mac can write to SSD at about 3GB/sec. Swapping is made faster by compressing data to be swapped so less data is written and then less data read back. Plus the effect of having more free memory. Compression is done in hardware. I think the processor has a not very well documented “compress 1024 byte” instruction.

Now the cheapest and biggest SSDs are much slower than that, and compression is much more powerful.