Ferenc Hegedus
Compression is usually discussed in terms of algorithm and level while there is another parameter that can have an equally important effect on the result: the logical block size(LBS).
KX have written a case study on the performance impact of the compression algos themselves – in this blog we are further experimenting with choosing various LBS to best fit our needs.
Logical block size affects the amount of data available to the compressor at once, the number of compressed blocks that must be read for a query, and the amount of work required to decompress those blocks. Moreover, kdb+ allows us to specify different compression setting to different columns using a dictionary.
This note explores the effect of changing LBS in isolation. We are going to show how different query patterns behave in terms of runtime, disk space and the count of OS read instructions.
The benchmark setup
The measurements below use a quote table with 5 000 000 records parted on sym(1000 instruments) and sorted by time(sym and time has ~equal distribution) inside. We aren’t going to clear the OS cache between tests(you ever ran the same query twice? I’m one of those!) – we want to know the cost of decompressing that we always pay when working with compressed files.
Logical block size and compression ratio
A larger logical block gives the compressor a larger region in which to find repeated patterns. This matters particularly for sorted or sparse columns, where similar values may be spread across a wider range. Here we compare the different algos for the sym and time columns with different LBS showing the achieved compression ratio in each case(the larger the better):
alg c | 12 14 16 17 18 20 ----------- | --------------------------------------------- gzip sym | 93.03 249.45 428.64 489.27 523.05 556.34 lz4hc sym | 100.2 172.16 212 220.3 224.71 228.12 snappy sym | 19.5 20.66 21 21.03 21.05 21.07 zstd sym | 130.9 456 1255.3 1719.3 1927.2 2205 gzip time | 1.36 1.38 1.38 1.38 1.38 1.38 lz4hc time | 1 1.01 1.03 1.05 1.06 1.06 snappy time | 1 1 1 1 1 1 zstd time | 1.18 1.17 1.14 1.14 1.2 1.14
The sym column shows the strongest effect. With gzip/zstd, increasing the block size from 12 to 20 produces a dramatic improvement in compression ratio. The same direction is visible with the other algos, although the gain is smaller.
The time column behaves differently. Its compression ratio changes very little(if at all). This is an important reminder that when considering block size for compression columns with different distributions can have very different sweet spots.
Compression ratio is not the only measure
A better compression ratio is valuable, but it is only one part of the cost. A query that consumes an entire column must read every block in that column regardless of whether the blocks are large or small. In that situation, fewer and larger blocks can reduce storage and I/O overhead, while the extra CPU cost of decompression may be a reasonable trade-off.
The following test measures read count for an aggregate over a dense column(5 000 000 rows):
select avg price from quote
The read counts were(for any algo):
alg | 12 14 16 17 18 20 ---- | ------------------------ zstd | 4888 2445 614 309 156 42
While time taken(relative, no compression is 1):
alg | 12 14 16 17 18 20 -----|-------------------------------- zstd | 42.24 12.12 6.60 5.57 5.42 8.33
For this whole-column query, the larger logical block sizes reduce the number of read system calls substantially. In this benchmark the reduction in I/O and the better compression outweigh the CPU cost of handling larger blocks.
Sequential ranges favour larger blocks
The size of the requested range also changes the balance. A single-row query cannot make much use of a large compression window, whereas a large continuous range can amortise the cost of reading and decompressing a block.
The next experiment queries continuous ranges of different lengths and measures read system call count for gzip:
select from quote where i in 100000+til x alg x | 12 14 16 17 18 20 ------------| ------------------- gzip 1 | 21 22 21 21 21 17 gzip 10 | 21 22 21 21 21 17 gzip 100 | 21 22 21 21 21 17 gzip 1000 | 23 25 21 21 21 17 gzip 10000 | 43 37 24 21 21 17 gzip 100000 | 263 169 57 39 30 21
For very small ranges the difference is negligible. As the range grows, the smaller blocks require more read system calls, while the larger blocks keep the read count low. For the largest range, the benchmark issued 263 read system calls at 12 LBS, but only 21 at 20 LBS.
The relative elapsed-time(non-compressed is 1) results show a similar, though less uniform pattern:
alg x | 12 14 16 17 18 20 ------------|-------------------------------- gzip 1 | 3.72 3.13 5.31 9.16 17.03 18.98 gzip 10 | 4.43 4.43 7.63 13 23.50 26.15 gzip 100 | 4.69 4.65 7.92 13.7 24.86 28.09 gzip 1000 | 5.14 5.34 7.28 12.4 22.40 24.56 gzip 10000 | 8.91 7.13 7.94 8.68 15.93 16.94 gzip 100000 | 13.9 9.45 8.65 9.14 10.54 12.88
With 20 LBS we managed to reach the same performance as 12 LBS, but we also saved disk space and reduced the number of I/O operations. Think about how that might affect you when you are reading the data from NFS or from a cloud-storage!
Random access has a different optimum
Random access exposes the main cost of a large logical block. If a query needs one value from a block, the system still has to read and decompress the whole block. Small blocks can therefore be much better for small random lookups.
The following test selects random rows and measures system read count:
select from quote where i in x?5000000
alg x | 12 14 16 17 18 20 ------------|---------------------------- gzip 1 | 21 22 21 21 21 21 gzip 10 | 56 54 52 52 52 46 gzip 100 | 342 327 314 293 253 129 gzip 1000 | 2501 2495 1509 899 479 141 gzip 10000 | 9878 7262 1857 941 482 141 gzip 100000 | 12268 7358 1857 941 482 141
For one random row, all block sizes have roughly the same read count. As the number of random rows increases, larger blocks become increasingly useful because the query touches enough data to benefit from them. At the same time, the result shows the opposite behaviour for genuinely small random lookups: larger blocks can bring in more irrelevant data.
Elapsed times can clear out the picture more on how well we are doing: larger random workloads can make larger blocks attractive:
Time taken in (relative, non-compressed is 1):
select from quote where i in x?5000000 alg x 12 14 16 17 18 20 ----------------------------------- gzip 1 2.3 1.2 2.4 4.5 8.3 30 gzip 10 5 5.2 12 21 40 145 gzip 100 25 32 95 162 251 504 gzip 1000 138 193 448 527 495 450 gzip 10000 664 596 528 516 475 463 gzip 100000 953 634 554 531 525 513
We can see that when random access increase from 1000->10000 we start being better off with larger LBS.
Column-wise compression reveals an opportunity
KDB+ allows different compression parameters for different columns. That makes it possible to avoid choosing one compromise for the entire table. Instead, compression can reflect the role and distribution of each column:
- A sorted, sparse or repetitive symbol column may benefit greatly from a larger logical block size.
- A timestamp or other column with little additional compressibility may gain almost nothing from a larger block.
- A column used for binary search or selective random access may prefer a smaller block size, even when a large sequential scan would prefer a larger one.
- A column that is normally scanned in full can often use a larger block size, because the query will consume most or all of each block anyway.
An asof-join on disk can benefit from the columnwise compression setting.
Here we have 50 000 000 quotes for 5 000 000 trades.
Compression settings:
fixed: zstd with 17 lbs
vs
colwise: zstd with sym, price comressed with 20 and 17 lbs, time left uncompressed
fixed compr db: 663M
vs
colwise compr db: 723M
aj[`sym`time;select from trade;select sym,time,quote:price from quote] comprType | time Read(MB) readCount ----------|------------------------ colwise | 1.48 19 221.2 fixed | 1.65 48 482.3
Time here is again relative to the non-compressed case. If not the execution time enhancement then the required I/O minimization can encourage us for customizing the compression settings in this case.
Starting points for harnessing lbs in compression
A fair advice for individuals planning on using different lbs for compression could be:
- Default 17 (128KB). It is what KX calls “quite reasonable“, and it sits sensibly in the middle. Do not go below 16 when your OS doesn’t support it, like in case of Windows.
- Drop to 14 (16KB) on columns that are binary-search or point-lookup targets.
- Time column can be left uncompressed. It is a frequent lookup column and is binary-searchable when sorted. Also, uncompressed columns work very well with memory mapping.
- On object-store or NFS-backed HDBs, floor at 17 and lean toward 18. Request latency dominates and small blocks will destroy you.
- Newly added, rarely touched column with scarce values – easy larger block like 20 (ex.: new exotic P&L column added to HDB, 90%+ empty/null values)
If after reading all this you decide to go with a mixed compression setting in your database let us know your feedback! I hope this note will help you to make use of different block size in compression, and you will appreciate the flexibility of kdb+ more 🙂
Share this:
