To: pgsql-performance@postgresql.org
From: Thomas Kellerer <spam_eater@gmx.net>
Subject: Re: Select count(*), the sequel
Date: Wed, 27 Oct 2010 22:54:11 +0200
Lines: 28
Message-ID: <iaa3hl$pkk$1@dough.gmane.org>
References: <4CB9D89E.7050701@vmsinfo.com>
	<20101016184443.GA4993@aart.is.rice.edu>
	<AANLkTik6ifMywZq7C1_MiHLafOQ53_OXreHYQdps3GqP@mail.gmail.com>
	<2091.1288133491@sss.pgh.pa.us> <op.vk82ubgueorkce@apollo13>
	<20101027204115.GB27429@aart.is.rice.edu>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows; U; Windows NT 5.1; en-US;
	rv:1.8.1.23) Gecko/20090812 Thunderbird/2.0.0.23 Mnenhy/0.7.6.666
In-Reply-To: <20101027204115.GB27429@aart.is.rice.edu>

Kenneth Marshall, 27.10.2010 22:41:
> Different algorithms have been discussed before. A quick search turned
> up:
>
> quicklz - GPL or commercial
> fastlz - MIT works with BSD okay
> zippy - Google - no idea about the licensing
> lzf - BSD-type
> lzo - GPL or commercial
> zlib - current algorithm
>
> Of these lzf can compress at almost 3.7X of zlib and decompress at 1.7X
> and fastlz can compress at 3.1X of zlib and decompress at 1.9X. The same
> comparison put lzo at 3.0X for compression and 1.8X decompress. The block
> design of lzl/fastlz may be useful to support substring access to toasted
> data among other ideas that have been floated here in the past.
>
> Just keeping the hope alive for faster compression.

What about a dictionary based compression (like DB2 does)?

In a nutshell: it creates a list of "words" in a page. For each word, the occurance in the db-block are stored and the actual word is removed from the page/block itself. This covers all rows on a page and can give a very impressive overall compression.
This compression is not done only on disk but in-memory as well (the page is loaded with the dictionary into memory).

I believe Oracle 11 does something similar.

Regards
Thomas