X-Original-To: pgsql-hackers-postgresql.org@postgresql.org Received: from localhost (mx1.hub.org [200.46.208.251]) by postgresql.org (Postfix) with ESMTP id C73F99FA65C for ; Tue, 25 Jul 2006 17:46:45 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.208.251]) (amavisd-new, port 10024) with ESMTP id 92607-06 for ; Tue, 25 Jul 2006 17:46:35 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey- Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by postgresql.org (Postfix) with ESMTP id D24009FA491 for ; Tue, 25 Jul 2006 17:46:35 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.13.6/8.13.6) with ESMTP id k6PKkTLh024310; Tue, 25 Jul 2006 16:46:29 -0400 (EDT) To: Josh Berkus cc: Gavin Sherry , Jie Zhang , pgsql-hackers@postgresql.org, Luke Lonergan Subject: Re: On-disk bitmap index patch In-reply-to: <44C6652C.1020203@agliodbs.com> References: <28525.1153698215@sss.pgh.pa.us> <28750.1153700718@sss.pgh.pa.us> <44C6652C.1020203@agliodbs.com> Comments: In-reply-to Josh Berkus message dated "Tue, 25 Jul 2006 11:38:36 -0700" Date: Tue, 25 Jul 2006 16:46:29 -0400 Message-ID: <24309.1153860389@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0.043 tagged_above=0 required=5 tests=AWL, SPF_HELO_PASS, SPF_PASS X-Spam-Level: X-Archive-Number: 200607/1220 X-Sequence-Number: 87075 Josh Berkus writes: > One particular compelling situation for on-disk bitmaps is for terabyte > tables where a btree index would not fit into memory. Index > performance for an index which is 10x or more the size of RAM really > sucks ... I can come up with some test results if you doubt that. Sure... > Also note that "low cardinality" is relative. For a 1 billion row > table, a column with 10,000 values is "low-cardinality", having around > 100,000 rows per value ... but that's still 0.01% of the table per > value, making index use still applicable. And your point is? Assuming a reasonable datatype like int4, a btree index on this table would occupy say 20GB (16 bytes per entry plus fillfactor overhead). The bitmap version would require 10,000 bitmaps of 1G bits apiece, or 1250GB (not even counting overhead). You need some wildly optimistic assumptions about the compressibility of the bitmaps to get even within hailing distance of the btree, let alone fit in RAM. A realistic assumption for the numbers you mention is that the bitmaps have 1-bits about 100 bits apart, which means you could get maybe 3-to-1 compression using the runlength scheme that's in there ... leaving the bitmap a factor of 20 bigger than the btree. AFAICS "low cardinality" has to mean just that, a few dozen distinct values at most, for this scheme to have any hope. regards, tom lane