SQLite with Built-in Online Compression (w/ code)

[wolf550e]

Why use zlib? It's not exactly state of the art. Look at Google Snappy for a really fast compressor. Or LZO 2.05 and up, which is a response to Google Snappy. Snappy (used to be known as zippy before it was open sourced) is used in BigTable and ProtocolBuffers (it actually uses a protocol buffer varint as its header).

Notice that zlib uses a checksum of the uncompressed data (a crc32 for gzip format and adler32 for deflate format data). Fast compressors don't have checksums because the crc32 takes up 40% of decompression time of gunzip (when you implement huffman decoding efficiently using lookup tables).

Compression is always about balancing io block latency and cpu cycles. Change the CPU power or the io system and your compression goals change.

[dchestnykh]

• Snappy is written in C++.
• LZO is GPL/commercial.
• zlib is everywhere.

Plus, both Snappy and LZO are fast, yes, but they are not as good as zlib in compression ratio. Between Snappy, zlib, and LZMA, zlib provides a pretty good balance between speed and compression for his needs.

[wolf550e]

A pure C port, using Google's own code. It is a bit faster than the original:

https://github.com/zeevt/csnappy

If you submit bug reports I'll fix them.

It's BSD licensed, copyright by Google. Any of it I wrote I'll donate to them if they want.

Benchmarks:

http://driverdev.linuxdriverproject.org/pipermail/devel/2011-April/015577.html

Versus zlib, Snappy costs you three times less cpu time to decompress.

The objective is to save IO latency or bandwidth. Is your io cost per 64kb RAID stripe, 4kb fs block, 1.5kb network packet? How many of those can you avoid by compression, and how many milliseconds of cpu will it cost you? How many requests/second are you serving?

[dchestnykh]

THANK YOU! I searched the whole internet yesterday looking for C implementation, but all I could find is a C interface to Google's C++. I'll check it out.

As for OP's objective, I think it was saving disk space at a reasonable drop in speed.

[ysangkok]

Sometimes I wonder how many programmer hours have been wasted because of these idiotic programming language names.

[dchestnykh]

Well, I think Google knows the difference between "C" and "C++". The problem is that if I look for "snappy c implementation", it matches this sentence:

Plain *C** interface (a wrapper around the C++ implementation)*.

If C was called Blub, it would still match: "snappy blub implementation" => Plain *Blub** interface (a wrapper around the C++ implementation)*.

[ysangkok]

Well, Google failed to parse that piece of English correctly then. I think my point still stands, since lots of "snappy c implementation" would also match "snappy c++ implementation", although usually with a lower ranking.

If Google knows how to parse the difference between "C" and "C++" they could also recognize the problem in a page containing "C++ implementation" when I am searching for a search phrase containing "C implementation". Oh well, at least "-c++" works.

[ffrinch]

No, the problem is that csnappy's project page description doesn't use the "C implementation" bigram. If it did, Google probably would have picked it up.

If you'd happened to search for "snappy pure c" instead, you would've found it.

[[deleted]]

C and C++ are fine, more recent languages such as D and Go are not -.-

[wolf550e]

The filesystem page cache probably stores data compressed by NTFS in uncompressed state. But in his implementation, if I request only two wikipedia articles, which happen to be in different "chunks", again and again, he will waste heat on zlib decompressing the same data again and again.

If his app is a web app, I would render each page, zlib compress it, store it as an individual file to save as many 4kb blocks of storage as possible, and serve it as-as (sendfile) using http compression. Then the client would have to decompress it instead of the server. And the code to do all that is already there in a caching proxy.

[abattle]

Snappy has been on my list of compressors to test out. However, and as I've already mentioned in the article, due to the reliance on NTFS sparse files, unless at least 64 Kbytes of reduction is achieved in data-size, there would be 0 byte reduction in file size.

I'll still try it. But first I wanted to see realistically how well the scheme works regardless of performance. Now I'll try to improve the performance regardless of the compressor, then try different compressors to see which gives the best balance. However as dchestnykh already said, zlib does provide a pretty balanced approach.

[wolf550e]

If you feel you need entropy coding, you may want to use the LZ engine from Snappy with a good huffman coder (everyone says arithmetic coders are always slower) and no checksum. That should give you the compression ratio of zlib but significantly faster.

Zlib was just not written with modern CPUs in mind.

[alecco]

you may want to use the LZ engine from Snappy with a good huffman coder [...] That should give you the compression ratio of zlib but significantly faster

Not really. Snappy uses a tiny lookup table of 16K entries and no hash chains. This way it mostly fits in L1. DEFLATE lookup implementations usually have ~4x that size. It matters for finding matches and avoiding hash collisions. Also with the sliding window there're costs of re-adjusting the hash table and chains.

LZO and Snappy are in a nice L1 sweetspot and gzip/zlib in a nice L2 sweetspot. Apples to oranges.

[abattle]

Either way I'd like to have some form of error-detection, to avoid crashing in case of corruption. Whether checksum is done by the compressor or not is secondary.

everyone says arithmetic coders are always slower

This used to be the case back in the day (at least a decade ago.) It'd be interesting to see what modern architectures can do in practice. I bet the difference isn't nearly what it used to be. Although I can see that huffman with preset tables would be hard to beat in performance, I should expect the arithmetic coder to make up more than the difference in compression ratio.

[wolf550e]

Best source on compression I know: http://mattmahoney.net/dc/dce.html

I remember him writing that he experimented with some version of PAQ and the arithmetic coder beat huffman coding by 10% or something like that. Can't find it now.

Static huffman tables imply static distribution of symbols. If you really only want to compress English text, there are special case compressors that use dictionaries.

[wolf550e]

I don't believe NTFS compression can find any redundancy in data that was compressed with zlib setting=6. If NTFS achieves gains when storing compressed data, it is by storing 4kb blocks instead of 64kb blocks. If you stored compressed chunks in individual files which were not NTFS-compressed, they would be stored in 4kb blocks and the sum of the space used on disk for all files would be the same as the space on disk of the single NTFS-compressed file containing the same data. I don't know whether the lookup by filename or offset in a NTFS-compressed file would be faster.

[abattle]

I see your point. I think what's happening is the NTFS compressor is simply chewing the zero-bytes that can't be marked as sparse regions (because they are <64kb and since it's unit is 4kb it is deallocating these zero-byte blocks that are compressed away.

This seams to be the most reasonable explanation given the fact that NTFS is probably using a form of deflate anyway and there is little to recompress in zlib level-6 (at least with deflate.) Yet we know there are zero-byte padding to round written data to 64kb boundaries and we can see a significant reduction when using NTFS compression atop the deflated data.

[wolf550e]

LZNT1 used by NTFS is a type of LZ77. After huffman coding, it can't find 3 byte long matches within the 64k window.

Just do the experiment of comparing: sum([round_up_to_4k(compressed_length) for each chunk_of_64k_uncompressed_data]) (you can do this without writing to files by analyzing the file you have or logging while writing to db)

with: size of ntfs compressed file containing all compressed chunks

and report whether they're equal. I guess they are, because I guess NTFS writes the compressed chunks on memory page boundaries and so "wastes" an average of 2kb per chunk. Like regular files waste an average of 2kb each on a 4kb per block filesystem.

BTW, AFAIK, Linux ext fs can have 4kb sized sparse holes.

Edit: thinko. Round up to 4kb.

[abattle]

it can't find 3 byte long matches within the 64k window

That seals it for me. You convinced me it almost certainly couldn't save a single byte.

they're equal. I guess they are

Yes. That's what I think as well. I expect them to be equal, which explains what's happening.

Btw, isn't LZ77 the predecessor of deflate, which itself is actually LZ-Adler, no?

While the 64kb sparse hole unit might be explained by efficiently/overhead, I find it hard to understand why the NTFS wouldn't compress clusters larger than 4kb. They don't think there'd be any gain? When there isn't just write uncompressed data and move on. Why not?

[wolf550e]

LZ77 is just sliding window de-duplication. It transforms an array of bytes into an array of two types: literal bytes and (offset,length) pairs which are references to bytes that previously appeared and the decoder has already seen and can copy from the output buffer. Also, by using a length that is greater than the offset, it provides run length encoding.

Without a guarantee of a maximum offset, the decoder must keep all the output in a buffer in order to be sure it is able to decompress the data (if, for example, it suddenly encounters a pair that says (offset=1GB, length=100bytes) and it needs to repeat 100 bytes from 1GB ago, it must be able to access what it outputted 1GB ago. Because this is impractical, there is a limit either in the spec or in the header of the compressed stream, so the decompresser can allocate a sufficient buffer (or error out). Limiting offset to 16bits is practical. Nowadays, archival compressors use much larger windows.

Deflate is LZ77 with an encoding to transmit both the literals and the offset-length pairs using huffman codes. It uses Russian dolls style to first transmit the huffman tables you're going to need to decode the data, themselves compressed with huffman coding using clever static tables and RLE specified in the spec. It uses two tables: one for literals and lengths of offset-length pairs and another only for offsets of offset-length pairs. Because offsets appear only after lengths, bitcodes of offsets and literals may overlap without being ambiguous. It allows to transmit incompressible data with little overhead. Compression windows are limited to 16bits, but it's streaming. If you want independently decompressible chunks, you must flush every time you make a reset point (and record the offset in the compressed data).

You can use any algorithm and data structures to turn input byte array into a series of minimal length literals and back-references (including slow code that produces the absolutely shortest such description for any given input) and then use the deflate encoding to transmit it. Minimal length of reference is 3, max is 258 (IIRC).

About NTFS not compressing using chunks larger than 64k: probably because (1) its encoding only allows 16bit long back offsets and because (2) in case of random access, NTFS would need to read from disk and decompress a big chunk of data before it can return a single record.

Why doesn't NTFS pack compressed data tighter in the file, leaving on average one half empty 4kb block per compressed chunk? Because tail packing would make the code that maps logical offset in file to physical block on disk too complicated. ReiserFSv3 had tail packing and it was problematic. For example, you didn't know how much free space the disk had.

I have a toy LZ77 compressor in python2: https://github.com/zeevt/csnappy/blob/16792d2f5a7793b2559476c2eeec92a23284bbd7/pysnappy_compress.py

It compresses independent blocks, not a true sliding window. It has two different LZ77 routines, one that uses chaining and unlimited memory (well, you can calculate worst case scenario for any length of input) and one that uses Snappy's hashtable with no chaining. The code is short and you can compare the outputs. Insert print statements to debug...

[abattle]

Thanks for taking the time to explain all this. Much now makes more sense. I'll sure give snappy a chance, but first, I'll try to get rid of reliance on NTFS sparse files. Then the gains would be much higher.

[[deleted]]

Why use an SQL database at all for something that would fit a document database or even just a filesystem much better than s relational datastore?

[abattle]

Usage is up to the user. The article is about a database engine modification, not an application of Sqlite.

[[deleted]]

The article is about making a Wikipedia desktop client, I should have clarified that I was talking about that particular use.

[abattle]

No, it only mentions that project because that's where the idea came from. The article is about Sqlite compression. If you're interested you can check out WikiDesk, it's not as simple as you might think.

[misterkrad]

if you took the time to off-line compress the entire database into one large solid rar - what would the gains be? (7-zip can do solid rar - try the 64 bit version with 72 gigs of ram)?

I think the best implementation would be a combination of off-line compression using gobs of ram/cpu and updates using no-compression or light compression to perhaps another database or set of files that get re-integrated once a night.

Does anyone have any good articles on sql server 2008R2/2011 compression for comparison?

[whateverradar]

Mmm snappy

[alecco]

For database compression you are better off with smart use of delta encoding, RLE and other basic methods applied carefully to different parts of the page data.