Re: Question about indexes

Greg Stark <gsstark(at)mit(dot)edu> writes:
>> Combining indexes via a bitmap intermediate step (which is not really
>> the same thing as bitmap indexes, IIUC) seems like a more robust
>> approach than relying on the index entries to be in ctid order.

> I would see that as the next step, But it seems to me it would be only a small
> set of queries where it would really help enough to outweigh the extra work of
> the sort.

What sort? The whole point of a bitmap is that it makes it easy to
visit the tuples in heap order. You scan the index, you set the
appropriate bits in the bitmap, and then you scan the bitmap and go to
the heap tuples that have their bits set. If you are using multiple
indexes you can AND or OR their results at the bitmap phase before you
go to the heap.

An implementation of this kind would not produce tuples in index order,
so if you have an ORDER BY to satisfy then you end up doing an explicit
sort after you have the tuples. It would be up to the planner to
consider this cost versus the advantages of being able to use multiple
indexes; we'd certainly want to keep the existing scan mechanism as an
available alternative. But if the query is suited to multiple indexes
I suspect it'd be a win pretty often.

> Note that the space saving of bitmap indexes is still a substantial factor.

I think you are still confusing what I'm talking about with a bitmap
index, ie, a persistent structure on-disk. It's not that at all, but
a transient structure built in-memory during an index scan.

I'm a little dubious that true bitmap indexes would be worth building
for Postgres. Seems like partial indexes cover the same sorts of
applications and are more flexible.

regards, tom lane