Skip site navigation (1) Skip section navigation (2)

Re: bitmap indexes - performance

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Robert Haas <robertmhaas(at)gmail(dot)com>
Cc: Leonardo F <m_lists(at)yahoo(dot)it>, pgsql-hackers(at)postgresql(dot)org
Subject: Re: bitmap indexes - performance
Date: 2010-07-01 15:21:26
Message-ID: 5147.1277997686@sss.pgh.pa.us (view raw or flat)
Thread:
Lists: pgsql-hackers
Robert Haas <robertmhaas(at)gmail(dot)com> writes:
> Hmm... no performance improvement?  That's not encouraging.

> The index being smaller ought to by itself provide some performance
> improvement if, say, the smaller index can fit in cache and the larger
> one can't.  With a 6-15x size difference, that's presumably not an
> implausible scenario.  But I guess the real point is to be able to AND
> and OR bitmap indices on multiple columns.  Not sure if this
> implementation supports that or not (I haven't read the patch) and how
> the performance compares to doing Bitmap Heap Scan -> BitmapAnd ->
> Bitmap Index Scan with btree indices.

In principle a bitmap index scan should be significantly faster if the
index can return the bitmap more or less "natively" rather than having
to construct it.  My recollection though is that a significant amount of
work is needed to make that happen, and that there is no existing patch
that tackled the problem.  So I'm not sure that this report should be
taken as indicating that there's no chance of a SELECT performance
improvement.  What it does say is that we have to do that work if we
want to make bitmap indexes useful.

In particular, I recall some discussions about developing a "streaming
API" whereby an index AM could return a bitmap page-by-page or so,
rather than having to construct the whole thing in-memory before
anything could happen.  This would be a huge win for AND/OR cases,
and even for a simple indexscan it would eliminate the existing startup
cost penalty for a bitmap scan.  Streaming like this would also
eliminate the problem of having to lossify large bitmaps in order to
not overrun memory.

			regards, tom lane

In response to

Responses

pgsql-hackers by date

Next:From: Robert HaasDate: 2010-07-01 15:40:22
Subject: Re: bitmap indexes - performance
Previous:From: Asko TiidumaaDate: 2010-07-01 15:19:46
Subject: reassign owned to change the ownership for op class and family

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group