Clickhouse: Feature request: add ability to apply delta or delta-of-delta encoding to numeric columns before compression

[valyala]

Clickhouse fits well for time-series DB from the performance point of view. But the compression ratio for the data stored in such databases may be further improved.

Tables in time-series DBs usually contain numeric values of two types: gauges (cpu usage, memory usage, network bandwidth usage, etc.) and counters (bytes transferred, requests processed, cpu cycles used, etc.).
Gauges are usually oscillate at a certain constant with a certain delta. So they compress well after delta encoding.
Counters are constantly incremented at a certain speed with the acceleration close to zero. So they compress well after delta-of-delta encoding.

It would be great if clickhouse would support delta and delta-of-delta encoding for numeric columns. This may be done via special type hints in CREATE TABLE:
```sql
CREATE TABLE t (
EventDate Date,
EventTime DateTime,

-- CPU usage in percents [0..100]. Use delta encoding before compression.
CPUUsage DeltaCoding(UInt8),

-- The number of requests processed. Use delta-of-delta encoding before compression.
RequestsProcessed DeltaDeltaCoding(UInt64),

-- Random number equally distributed in the range [0...2^32).
-- Do not use any encoding before compression, since it has no sense.
RandomNum UInt32

) ENGINE = MergeTree(...)

[pavel-odintsov]

Agree with it. Would be nice to have such option. I tried to put big number of metrics to CH and compression rate wasn't so cool :(

[Civil]

I also agree with that and even more - I think for TSDBs it might worth to implement some customized delta-delta encodings, e.x. how it's done in Prometheus v2 storage.

[valyala]

This would be useful for projects similar to https://github.com/s4z/prom2click , cc'ing @s4z.

[alexey-milovidov]

Totally agree.
We should have the ability to specify custom compression codec per column.

[AlekSi]

It will be useful for https://github.com/Percona-Lab/PromHouse

[mattbostock]

I'd like to give this a go but I'm new to the project. Would anyone more familiar with it be able to give me some pointers on the implementation, specifically adding a custom compression codec per column?

[alexey-milovidov]

Our compression format is quite simple.
Look at CompressedWriteBuffer and CompressedReadBufferBase for reference.

In short, it is the following:

Compressed data is formed of blocks, one after the other. Blocks are completely independent.
Each block is:

/** The compressed block format is as follows:
  *
  * The first 16 bytes are the checksum from all other bytes of the block. Now only CityHash128 is used.
  * In the future, you can provide other checksums, although it will not be possible to make them different in size.
  *
  * The next byte specifies the compression algorithm. Then everything depends on the algorithm.
  *
  * 0x82 - LZ4 or LZ4HC (they have the same format).
  *
  * NOTE: Why is 0x82?
  * Originally only QuickLZ was used. Then LZ4 was added.
  * The high bit is set to distinguish from QuickLZ, and the second bit is set for compatibility,
  *  for the functions qlz_size_compressed, qlz_size_decompressed to work.
  * Although now such compatibility is no longer relevant.
  *
  * 0x90 - ZSTD
  *
  *        Next 4 bytes - the size of the compressed data, taking into account this 8-byte header; 
  *        Next 4 bytes is the size of the uncompressed data.
  *
  * All sizes are little endian.
  */

What we want to change:

1. Single byte is not enough to identify the compression method, because we want to allow nested algorithms. For example, LZ4 of Delta (two algorithms stacked one after the other). We want to encode arbitary large sequence of compression algorithms; and each algorithm may have parameters that affect compressed format.
   To do this while maintaining backward compatibility, we may reserve a range with continuation bits - that will mean - look at the next byte.

2. Now we are stuck with single variant of checksum (CityHash128 exactly from CityHash version 1.0.2). Sometimes we want to use different checksums: xxhash for example. We can encode it in the same place as compression method.

3. As we will add the support of many compression algorithms, it's reasonable to extract switch/case to a separate interface and create a factory.

After we will add this support in block format, we can extend CREATE syntax to allow specifying preferred algorithms. Example: CREATE TABLE t (x UInt32 COMPRESSION LZ4(BLOSC))

But explicit specifying compression method for columns is not the only choice.
For example, we may want to implement the following features:

• compression of old/cold data with different algo or with higher compression level during merges (we already have this option, look at config.xml, compression section)
• background re-compression of data during idle times;
• adapt compression level to data ingestion rate during inserts;
• choosing somewhat optimal compression method by compressing blocks with slightly different settings;

It's unclear, how we can configure these possible options?

[alexey-milovidov]

We decided the following:

For every column in a table it will be possible to specify a list of compression codecs stacked together.
Example:

x UInt64 CODEC(Delta, LZ4(1))

• it means, that Delta codec will be applied, then LZ4 with parameter 1.

If codec is specified for a column, it will have highest priority over other (global) compression settings.

[Sindbag]

I will take that.

[otisg]

On https://clickhouse.yandex/docs/en/roadmap/ I see compression is scheduled for Q2 2018. Does it mean somebody from CH team will start working on better compression then, or can external contributors provide PRs earlier than that? For example, it looks like @Sindbag is saying he is up for doing it?

[Sindbag]

@otisg , I am doing it under control of the ClickHouse team, as external employee.

[zhang2014]

What is the current state of this issue? I plan to implement it. @alexey-milovidov

[Sindbag]

@zhang2014 I am doing the task, plan to pull request soon.

[otisg]

Nice. I know this will vary from situation to situation, but have you done any work to see how savings one could expect from this compression and what the price of that might be in terms of increased CPU usage?

[Sindbag]

@otisg well, currently I did not precisely benchmark the performance, but it is planned and, I expect, will be packed with other tests.

[sundy-li]

@Sindbag Is there any new progress about this feature you can share with us?
For example, will the implementation refer to gorilla and influxdb (delta compression , XOR compression etc )?

This feature could make ClickHouse perform much better on the time-series Data monitor scene. We are really very urgent to see that.

[alexey-milovidov]

Fixed.

[nvartolomei]

Closed in https://github.com/yandex/ClickHouse/commit/8cd1e8c21dcd65c4bfe8815b582bf7874842014a.