Re: Table and Index compression

First, a few things that I forgot to mention in the previous message :

> I like the idea too, but I think there are some major problems to
> solve. In particular I think we need a better solution to blocks
> growing than sparse files.

Sparse files allow something great : to test this concept in real life,
with a length of code that is shorter than this email.

> The main problem with using sparse files is that currently postgres is
> careful to allocate blocks early so it can fail if there's not enough
> space. With your sparse file solution Postgres might only find out
> there's no space after it has already committed a transaction.
> bgwriter has no good course of action to take if it finds out there's
> nowhere to put the data it has in shared buffers.

Yes, that is a big problem.

Note that the same problem can happen if you use a filesystem that
supports compression :

- you preallocate a file full of empty blocks
- filesystem compresses it well, says it fits
- you fill it with data that compresses much worse than zeros
- at some point one of the write() calls fails with a disk full error

This would be an interesting argument in the "can we use compressed ZFS on
postgres" debate...

Also, about compressed NTFS : it can give you disk-full errors on read().
While this may appear stupid, it is in fact very good.
When you read() something compressed, NTFS will reserve the space on disk
to re-write this data, assuming the worst compression, so your app fails
early (on read, not on write). If there is not enough space on the volume,
read() will fail with a disk full error. Many applications do not expect
this.

On the other hand, filling a disk completely is a never a good idea, since
it generally triggers fragmentation so extreme that the only way to
recover is to go buy another harddisk and copy your data.

As a side note, I have also tested lzjb (the ZFS compressor) and lzo is
much faster, and compresses much better (sometimes 2x better).

Back to the point of how to handle disk full errors :
- we could write a file the size of shared_buffers at startup
- if a write() reports disk full, delete the file above
- we now have enough space to flush all of shared_buffers
- flush and exit gracefully

This will waste disk space. Of course... but the purpose of compression is
not to save disk space, it is to have a faster database.
Also, if you use compression,
- you'll do it because your database is much bigger than shared_buffers,
so the wasted space is not huge.
- you'll use a smaller shared_buffers than usual, because shared_buffers
contains uncompressed pages, and you'll want to use lots of OS disk cache
to cache compressed data.

Doesn't seem too crazy to me.

> But I think even if you solve that it's not really a good long-term
> solution. We don't know how the OS handles block allocation for this
> type of file. I'm actually moderately surprised it isn't skipping
> enough blocks assuming you'll allocate them eventually. Even if it
> does handle it the way you expect what happens when you do grow a
> block, it'll have to allocate it way out of the way and we have no way
> to repair that discontinuity later.

I made a quick check before implementing it, using python scripts to play
with sparse files on ext3 :

- writing a sparse file is a bit (not much) slower than a regular file,
- reading from a non-fragmented sparse file is as fast as reading a
regular file
- holes do not eat OS disk cache (which is the most interesting point)
- reading from cache is as fast as reading a regular file (and faster if
you don't read the holes because you know they are holes, which is the
case here)

And, also, growing a sparse file by plugging the holes in it WILL allocate
blocks all over the place and render IO extremely inefficient.
You can defrag it, of course (using fs-specific tools or just cpio), but
that's not "high-availability"...

> Also, the way you've prellocated blocks effectively nails the maximum
> compression at 2x. That seems to be leaving a lot of money on the
> table.

Yes, it does, but there are a few subtleties.

First, about preallocation : I had to implement this, because of the way
the files are extended.
Since first an empty block is written, it will compress well, to 1 OS
page. When, later, this block is written again with data, it will compress
to a larger amount of pages, which will trigger allocation all over the
place. In testing, the resulting sparse file is slow in the of the "forget
it" kind...

The file could also be non-sparse : in this case, no disk space is saved.

Not saving disk space is OK with me : disks are really cheap these days.

I know this sounds crazy ;) but as I said above, compression is meant to
save expensive resources. When you use H-264 to compress 1TB of raw video
to 1GB of compressed video, you save an expensive resource (0.999 TB of
harddisk). But if you use lzo to compress 40GB of database down to 20GB,
you save maybe $3 in disk space, which is ludicrous. However, you also
save much more expensive resources : disk throughput and RAM OS cache. So
it might really pay off.

So, a non-sparse file would work well for random accesses too, since we
only read the parts of it that contain compressed data, and the "wasted"
pages would never be touched.

However it would have drawbacks :

- seq scan would not be able to skip the "empty" pages, so it would have
no benefit whatsoever
- the empty pages, read-ahead by the OS, would pollute the disk cache
- the empty pages would also pollute the controller's cache and the disks'
internal caches

So, a balance has to be reached on how much OS pages (4K on Linux) to
preallocate for a Postgres block (16K or 32K to get good compression).

If you preallocate too little, adding data (INSERT, UPDATEs) will heavily
fragment the file.
If you preallocate too much, seq scan will be slower and perhaps cache
will be wasted (but it will still be much faster than the huge seek-fest
which happens if you preallocate too little).

How many OS pages to preallocate for a postgres block should be specified
by the user.

- If you intend to modify the table contents, you should preallocate a bit
more.
- If the table will be mostly read-only, a tight fit is okay.

A nice thing is that it makes read-only tables a bit redundant. Basically,
if you ask postgres
"CLUSTER or VAC FULL this table, and compress it, not preallocating
anything more than necessary"
You will get a table and indexes that are well compressed, but updates,
deletes, will be slow, so it is a read-mostly table.

If you use partitions, the current partition can be uncompressed (or
compressed with a generous pre-allocation), but the past partitions, which
are usually read-only, can be compressed tight, and their indexes too.

Then you could change the pre-allocation value for this table to
preallocate more, and INSERT into it, no problem, except for the indexes,
for which you'd need to specify beforehand to preallocate a bit more pages
to allow for growing index pages...

So, how many pages to preallocate is a tuning parameter, that should have
a reasonable default, but be user-settable, per-relation (table, index...)

Note that if a page contains lots of dead rows which are similar except a
few updated columns, compression will exploit this redundancy.

Here are some stats on some tables of more than 300K rows :

* Table with lots of columns including a TEXT column of a few hundred
bytes, containing french text, which is usually too short for TOASTING :
Size : 314.69 MB
Paged Size : 133.24 MB
Unpaged efficiency : 2.77
Paged Efficiency : 2.36
pages | count
1 | 16
2 | 848
3 | 4451
4 | 4730
5 | 25

The above is a histogram : for instance 4730 32K postgresql blocks
compressed to 4 4K-pages (a ratio of 2X), and only 16 postgres blocks
compressed to 4K.

"Size" is uncompressed size
"Paged Size" is the sum of all 4K which contain compressed data
"Unpaged Efficiency" is (raw data) / (compressed data), showing compressor
performance.
"Paged Efficiency" is computed from the real number of pages used, so it
is the interesting metric.

In this case, efficiency is 2.36 because some pages compress better than
2X, but if we preallocate 16K for each 32K page, real efficiency will be
2X.
We can see, also, that 25 blocks would need some extra allocation. This is
a really small percentage of the table, so not significant to speed.

* GIN fulltext index on text field of above table

Size : 136.75 MB
Paged Size : 48.04 MB
Unpaged efficiency : 3.63
Paged Efficiency : 2.85
pages | count
1 | 1528
2 | 470
3 | 944
4 | 172
5 | 1262

* GIST fulltext index on text field of above table

annonces_ts_gist
Size : 63.84 MB
Paged Size : 33.89 MB
Unpaged efficiency : 2.14
Paged Efficiency : 1.88
pages | count
1 | 3
2 | 32
3 | 165
4 | 1103
5 | 739
6 | 1

* table with 32 columns including a few TEXT fields which contain at most
a few chars

Size : 393.50 MB
Paged Size : 127.24 MB
Unpaged efficiency : 3.83
Paged Efficiency : 3.09
pages | count
2 | 5207
3 | 7381
4 | 4

* btree on DATE column of above table

Size : 56.34 MB
Unpaged efficiency : 2.63
Paged Efficiency : 2.08
pages | count
1 | 2
2 | 1
3 | 282
4 | 1518

* btree on field "zipcode" of above table

Size : 56.34 MB
Paged Size : 27.04 MB
Unpaged efficiency : 2.90
Paged Efficiency : 2.67
pages | count
1 | 2
2 | 2
3 | 1794
4 | 5

* gist index on GPS coordinates (every row has (lat,lon)) of above table

Size : 196.47 MB
Paged Size : 39.79 MB
Unpaged efficiency : 6.93
Paged Efficiency : 4.94
pages | count
1 | 2486
2 | 3704
3 | 96
4 | 1

Note that the 32 column table is 400MB... and this gist index is almost
200 MB.
This table has 770 MB of indexes on it...
Compression shrinks the table to 127 MB and indexes to a total of about
300 MB.

* table of (increasing timestamp, 1 SERIAL, 1 increasing INT, 3 INT
columns which contain random() data)

Size : 344.06 MB
Paged Size : 215.02 MB
Unpaged efficiency : 1.97
Paged Efficiency : 1.60
pages | count
1 | 1
5 | 11009

* multicolumn btree on (int, timestamp) above

Size : 153.19 MB
Paged Size : 57.42 MB
Unpaged efficiency : 2.73
Paged Efficiency : 2.67
pages | count
1 | 3
3 | 4899

* btree on int column above

Size : 102.06 MB
Paged Size : 63.73 MB
Unpaged efficiency : 1.87
Paged Efficiency : 1.60
pages | count
1 | 2
2 | 1
4 | 3
5 | 3260

As you can see, efficiency varies widely between average (1.6), good
(2-2.5), and amazing (almost 5) depending on what is compressed.

> To handle read-write tables I think we would need to directly
> implement the kind of indirection layer that you're getting out of the
> filesystem's block layer currently. That would let you allocate enough
> blocks to hold the data uncompressed and then free up those blocks
> once you're sure the data is compressible.

Just like NTFS does, then ?

> One possibility is to handle only read-only tables. That would make
> things a *lot* simpler. But it sure would be inconvenient if it's only
> useful on large static tables but requires you to rewrite the whole
> table -- just what you don't want to do with large static tables -- to
> get the benefit.

See above : read-mostly table that you can still update (but it will be
very slow) or insert into (if you change the preallocation setting).

I forgot to talk about SSDs in the previous message. SSDs are quite
expensive, but seek really fast. Saving disk space would be good on a SSD,
because the price per byte is much higher. And since SSDs seek very fast,
they probably wouldn't be bothered that much by sparse blocks being
allocated all over the place. Also the price of SSDs means you wouldn't
make a monster RAID out of them, so the CPU could decompress faster than
the disk in a seqscan. This would need a test.

Ah, I would like to know a thing : if I add a 2-byte field to the postgres
page header, which contains the compressed length, will I get any problems
? (ie. do some pages use a non-standard header ?)

I need to modify a few things and add comments, then will submit a patch
(not for committing, but for hacking).