Skip to content

Commit 31e1793

Browse files
bmomjianbmomjian
committed
Add bitmap email to archive.
1 parent 2e32eca commit 31e1793

File tree

1 file changed

+139
-3
lines changed

1 file changed

+139
-3
lines changed

‎doc/TODO.detail/performance

Lines changed: 139 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -345,7 +345,7 @@ From owner-pgsql-hackers@hub.org Tue Oct 19 10:31:10 1999
345345
Received: from renoir.op.net (root@renoir.op.net [209.152.193.4])
346346
by candle.pha.pa.us (8.9.0/8.9.0) with ESMTP id KAA29087
347347
for <maillist@candle.pha.pa.us>; Tue, 19 Oct 1999 10:31:08 -0400 (EDT)
348-
Received: from hub.org (hub.org [216.126.84.1]) by renoir.op.net (o1/$Revision: 1.11 $) with ESMTP id KAA27535 for <maillist@candle.pha.pa.us>; Tue, 19 Oct 1999 10:19:47 -0400 (EDT)
348+
Received: from hub.org (hub.org [216.126.84.1]) by renoir.op.net (o1/$Revision: 1.12 $) with ESMTP id KAA27535 for <maillist@candle.pha.pa.us>; Tue, 19 Oct 1999 10:19:47 -0400 (EDT)
349349
Received: from localhost (majordom@localhost)
350350
by hub.org (8.9.3/8.9.3) with SMTP id KAA30328;
351351
Tue, 19 Oct 1999 10:12:10 -0400 (EDT)
@@ -454,7 +454,7 @@ From owner-pgsql-hackers@hub.org Tue Oct 19 21:25:30 1999
454454
Received: from renoir.op.net (root@renoir.op.net [209.152.193.4])
455455
by candle.pha.pa.us (8.9.0/8.9.0) with ESMTP id VAA28130
456456
for <maillist@candle.pha.pa.us>; Tue, 19 Oct 1999 21:25:26 -0400 (EDT)
457-
Received: from hub.org (hub.org [216.126.84.1]) by renoir.op.net (o1/$Revision: 1.11 $) with ESMTP id VAA10512 for <maillist@candle.pha.pa.us>; Tue, 19 Oct 1999 21:15:28 -0400 (EDT)
457+
Received: from hub.org (hub.org [216.126.84.1]) by renoir.op.net (o1/$Revision: 1.12 $) with ESMTP id VAA10512 for <maillist@candle.pha.pa.us>; Tue, 19 Oct 1999 21:15:28 -0400 (EDT)
458458
Received: from localhost (majordom@localhost)
459459
by hub.org (8.9.3/8.9.3) with SMTP id VAA50745;
460460
Tue, 19 Oct 1999 21:07:23 -0400 (EDT)
@@ -1006,7 +1006,7 @@ From pgsql-general-owner+M2497@hub.org Fri Jun 16 18:31:03 2000
10061006
Received: from renoir.op.net (root@renoir.op.net [207.29.195.4])
10071007
by candle.pha.pa.us (8.9.0/8.9.0) with ESMTP id RAA04165
10081008
for <pgman@candle.pha.pa.us>; Fri, 16 Jun 2000 17:31:01 -0400 (EDT)
1009-
Received: from hub.org (root@hub.org [216.126.84.1]) by renoir.op.net (o1/$Revision: 1.11 $) with ESMTP id RAA13110 for <pgman@candle.pha.pa.us>; Fri, 16 Jun 2000 17:20:12 -0400 (EDT)
1009+
Received: from hub.org (root@hub.org [216.126.84.1]) by renoir.op.net (o1/$Revision: 1.12 $) with ESMTP id RAA13110 for <pgman@candle.pha.pa.us>; Fri, 16 Jun 2000 17:20:12 -0400 (EDT)
10101010
Received: from hub.org (majordom@localhost [127.0.0.1])
10111011
by hub.org (8.10.1/8.10.1) with SMTP id e5GLDaM14477;
10121012
Fri, 16 Jun 2000 17:13:36 -0400 (EDT)
@@ -1513,3 +1513,139 @@ Cheerio,
15131513
Link.
15141514

15151515

1516+
From pgsql-hackers-owner+M20329@postgresql.org Tue Mar 19 18:00:15 2002
1517+
Return-path: <pgsql-hackers-owner+M20329@postgresql.org>
1518+
Received: from postgresql.org (postgresql.org [64.49.215.8])
1519+
by candle.pha.pa.us (8.11.6/8.10.1) with ESMTP id g2K00EA02465
1520+
for <pgman@candle.pha.pa.us>; Tue, 19 Mar 2002 19:00:14 -0500 (EST)
1521+
Received: from postgresql.org (postgresql.org [64.49.215.8])
1522+
by postgresql.org (Postfix) with SMTP
1523+
id 8C7164763EF; Tue, 19 Mar 2002 18:22:08 -0500 (EST)
1524+
Received: from CopelandConsulting.Net (dsl-24293-ld.customer.centurytel.net [209.142.135.135])
1525+
by postgresql.org (Postfix) with ESMTP id E4DAD475F1F
1526+
for <pgsql-hackers@postgresql.org>; Tue, 19 Mar 2002 18:02:17 -0500 (EST)
1527+
Received: from mouse.copelandconsulting.net (mouse.copelandconsulting.net [192.168.1.2])
1528+
by CopelandConsulting.Net (8.10.1/8.10.1) with ESMTP id g2JN0jh13185;
1529+
Tue, 19 Mar 2002 17:00:45 -0600 (CST)
1530+
X-Trade-Id: <CCC.Tue, 19 Mar 2002 17:00:45 -0600 (CST).Tue, 19 Mar 2002 17:00:45 -0600 (CST).200203192300.g2JN0jh13185.g2JN0jh13185@CopelandConsulting.Net.
1531+
Subject: Re: [HACKERS] Bitmap indexes?
1532+
From: Greg Copeland <greg@CopelandConsulting.Net>
1533+
To: Matthew Kirkwood <matthew@hairy.beasts.org>
1534+
cc: Oleg Bartunov <oleg@sai.msu.su>,
1535+
PostgresSQL Hackers Mailing List <pgsql-hackers@postgresql.org>
1536+
<Pine.LNX.4.33.0203192118140.29494-100000@sphinx.mythic-beasts.com>
1537+
<Pine.LNX.4.33.0203192118140.29494-100000@sphinx.mythic-beasts.com>
1538+
Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature";
1539+
boundary="=-Ivchb84S75fOMzJ9DxwK"
1540+
X-Mailer: Evolution/1.0.2
1541+
Date: 19 Mar 2002 17:00:53 -0600
1542+
Message-ID: <1016578854.14670.450.camel@mouse.copelandconsulting.net>
1543+
MIME-Version: 1.0
1544+
Precedence: bulk
1545+
Sender: pgsql-hackers-owner@postgresql.org
1546+
Status: OR
1547+
1548+
--=-Ivchb84S75fOMzJ9DxwK
1549+
Content-Type: text/plain
1550+
Content-Transfer-Encoding: quoted-printable
1551+
1552+
On Tue, 2002-03-19 at 15:30, Matthew Kirkwood wrote:
1553+
> On Tue, 19 Mar 2002, Oleg Bartunov wrote:
1554+
>=20
1555+
> Sorry to reply over you, Oleg.
1556+
>=20
1557+
> > On 13 Mar 2002, Greg Copeland wrote:
1558+
> >
1559+
> > > One of the reasons why I originally stated following the hackers list=
1560+
is
1561+
> > > because I wanted to implement bitmap indexes. I found in the archive=
1562+
s,
1563+
> > > the follow link, http://www.it.iitb.ernet.in/~rvijay/dbms/proj/, which
1564+
> > > was extracted from this,
1565+
> > > http://groups.google.com/groups?hl=3Den&threadm=3D01C0EF67.5105D2E0.m=
1566+
ascarm%40mascari.com&rnum=3D1&prev=3D/groups%3Fq%3Dbitmap%2Bindex%2Bgroup:c=
1567+
omp.databases.postgresql.hackers%26hl%3Den%26selm%3D01C0EF67.5105D2E0.masca=
1568+
rm%2540mascari.com%26rnum%3D1, archive thread.
1569+
>=20
1570+
> For every case I have used a bitmap index on Oracle, a
1571+
> partial index[0] made more sense (especialy since it
1572+
> could usefully be compound).
1573+
1574+
That's very true, however, often bitmap indexes are used where partial
1575+
indexes may not work well. It maybe you were trying to apply the cure
1576+
for the wrong disease. ;)
1577+
1578+
>=20
1579+
> Our troublesome case (on Oracle) is a table of "events"
1580+
> where maybe fifty to a couple of hundred are "published"
1581+
> (ie. web-visible) at any time. The events are categorised
1582+
> by sport (about a dozen) and by "event type" (about five).
1583+
> We never really query events except by PK or by sport/type/
1584+
> published.
1585+
1586+
The reason why bitmap indexes are primarily used for DSS and data
1587+
wherehousing applications is because they are best used on extremely
1588+
large to very large tables which have low cardinality (e.g, 10,000,000
1589+
rows having 200 distinct values). On top of that, bitmap indexes also
1590+
tend to be much smaller than their "standard" cousins. On large and
1591+
very tables tables, this can sometimes save gigs in index space alone
1592+
(serious space benefit). Plus, their small index size tends to result
1593+
in much less I/O (serious speed benefit). This, of course, can result
1594+
in several orders of magnitude speed improvements when index scans are
1595+
required. As an added bonus, using AND, OR, XOR and NOT predicates are
1596+
exceptionally fast and if implemented properly, can even take advantage
1597+
of some 64-bit hardware for further speed improvements. This, of
1598+
course, further speeds look ups. The primary down side is that inserts
1599+
and updates to bitmap indexes are very costly (comparatively) which is,
1600+
yet again, why they excel in read-only environments (DSS & data
1601+
wherehousing).
1602+
1603+
It should also be noted that RDMS's, such as Oracle, often use multiple
1604+
types of bitmap indexes. This further impedes insert/update
1605+
performance, however, the additional bitmap index types usually allow
1606+
for range predicates while still making use of the bitmap index. If I'm
1607+
not mistaken, several other types of bitmaps are available as well as
1608+
many ways to encode and compress (rle, quad compression, etc) bitmap
1609+
indexes which further save on an already compact indexing scheme.
1610+
1611+
Given the proper problem domain, index bitmaps can be a big win.
1612+
1613+
>=20
1614+
> We make a bitmap index on "published", and trust Oracle to
1615+
> use it correctly, and hope that our other indexes are also
1616+
> useful.
1617+
>=20
1618+
> On Postgres[1] we would make a partial compound index:
1619+
>=20
1620+
> create index ... on events(sport_id,event_type_id)
1621+
> where published=3D'Y';
1622+
1623+
1624+
Generally speaking, bitmap indexes will not serve you very will on
1625+
tables having a low row counts, high cardinality or where they are
1626+
attached to tables which are primarily used in an OLTP capacity.=20
1627+
Situations where you have a low row count and low cardinality or high
1628+
row count and high cardinality tend to be better addressed by partial
1629+
indexes; which seem to make much more sense. In your example, it sounds
1630+
like you did "the right thing"(tm). ;)
1631+
1632+
1633+
Greg
1634+
1635+
1636+
--=-Ivchb84S75fOMzJ9DxwK
1637+
Content-Type: application/pgp-signature; name=signature.asc
1638+
Content-Description: This is a digitally signed message part
1639+
1640+
-----BEGIN PGP SIGNATURE-----
1641+
Version: GnuPG v1.0.6 (GNU/Linux)
1642+
Comment: For info see http://www.gnupg.org
1643+
1644+
iD8DBQA8l8Ml4lr1bpbcL6kRAhldAJ9Aoi9dwm1OteZjySfsd1o42trWLACfegQj
1645+
OEV6eO8MnBSlbJMHiQ08gNE=
1646+
=PQvW
1647+
-----END PGP SIGNATURE-----
1648+
1649+
--=-Ivchb84S75fOMzJ9DxwK--
1650+
1651+

0 commit comments

Comments
 (0)