X-Original-To: pgsql-hackers-postgresql.org@postgresql.org Received: from localhost (wm.hub.org [200.46.204.128]) by postgresql.org (Postfix) with ESMTP id 373959FB1C6 for ; Mon, 24 Jul 2006 21:48:16 -0300 (ADT) Received: from postgresql.org ([200.46.204.71]) by localhost (mx1.hub.org [200.46.204.128]) (amavisd-new, port 10024) with ESMTP id 09631-02 for ; Tue, 25 Jul 2006 00:48:08 +0000 (UTC) X-Greylist: delayed 18:24:02.843067 by SQLgrey- Received: from mail.mi8.com (d01gw04.mi8.com [63.240.6.44]) by postgresql.org (Postfix) with ESMTP id 4BA889FA441 for ; Mon, 24 Jul 2006 21:48:07 -0300 (ADT) Received: from 172.16.1.112 by mail.mi8.com with ESMTP (- Welcome to Mi8 Corporation www.Mi8.com (D4)); Mon, 24 Jul 2006 20:48:01 -0400 X-Server-Uuid: C8FB4D43-1108-484A-A898-3CBCC7906230 Received: from MI8NYCMAIL05.Mi8.com ([172.16.1.189]) by D01SMTP02.Mi8.com with Microsoft SMTPSVC(6.0.3790.1830); Mon, 24 Jul 2006 20:48:01 -0400 Received: from 71.146.16.17 ([71.146.16.17]) by MI8NYCMAIL05.Mi8.com ( [172.16.1.77]) via Exchange Front-End Server mi8owa.mi8.com ( [172.16.1.106]) with Microsoft Exchange Server HTTP-DAV ; Tue, 25 Jul 2006 00:48:00 +0000 User-Agent: Microsoft-Entourage/11.2.5.060620 Date: Mon, 24 Jul 2006 17:47:59 -0700 Subject: Re: On-disk bitmap index patch From: "Jie Zhang" To: "Hannu Krosing" , "Tom Lane" cc: "Gavin Sherry" , pgsql-hackers@postgresql.org, "Luke Lonergan" Message-ID: Thread-Topic: [HACKERS] On-disk bitmap index patch Thread-Index: Acavg/mcOENN3xt3EduI7QARJITXBg== In-Reply-To: <1153749575.2909.3.camel@localhost.localdomain> MIME-Version: 1.0 X-OriginalArrivalTime: 25 Jul 2006 00:48:01.0001 (UTC) FILETIME=[FACDDD90:01C6AF83] X-WSS-ID: 68DBB5CB3IG614846-01-01 Content-Type: text/plain; charset=iso-8859-1 Content-Transfer-Encoding: quoted-printable X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=1.635 tagged_above=0 required=5 tests=FORGED_RCVD_HELO, RCVD_NUMERIC_HELO X-Spam-Level: * X-Archive-Number: 200607/1102 X-Sequence-Number: 86957 On 7/24/06 6:59 AM, "Hannu Krosing" wrote: > =DChel kenal p=E4eval, P, 2006-07-23 kell 20:25, kirjutas Tom Lane: >> Gavin Sherry writes: >>> On Sun, 23 Jul 2006, Tom Lane wrote: >>>> However, the main problem I've got with this is that a new index AM is= a >>>> pretty large burden, and no one's made the slightest effort to sell >>>> pghackers on taking this on. >>=20 >>> For low cardinality sets, bitmaps greatly out perform btree. >>=20 >> If the column is sufficiently low cardinality, you might as well just do >> a seqscan --- you'll be hitting most of the heap's pages anyway. I'm >> still waiting to be convinced that there's a sweet spot wide enough to >> justify supporting another index AM. (I'm also wondering whether this >> doesn't overlap the use-case for GIN.) >=20 > IIRC they quoted the cardinality of 10000 as something that is still > faster than btree for several usecases. >=20 > And also for AND-s of several indexes, where indexes are BIG, your btree > indexes may be almost as big as tables but the resulting set of pages is > small. Yeah, Hannu points it out very well -- the bitmap index works very well whe= n columns have low cardinalities and AND operations will produce small number of results. Also, the bitmap index is very small in low cardinality cases, where the btree tends to take up at least 10 times more space.