Re: Question about indexes

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Greg Stark <gsstark(at)mit(dot)edu>
Cc: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Question about indexes
Date: 2004-01-28 14:59:11
Message-ID: 18092.1075301951@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

Greg Stark <gsstark(at)mit(dot)edu> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>> What sort?

> To build the in-memory bitmap you effectively have to do a sort.

Hm, you're thinking that the operation of inserting a bit into a bitmap
has to be at least O(log N). Seems to me that that depends on the data
structure you use. In principle it could be O(1), if you use a true
bitmap (linear array) -- just index and set the bit. You might be right
that practical data structures would be O(log N), but I'm not totally
convinced.

> If the tuples come out of the index in heap order then you can combine
> them without having to go through that step.

But considering the restrictions implied by that assumption --- no range
scans, no non-btree indexes --- I doubt we will take the trouble to
implement that variant. We'll want to do the generalized bitmap code
anyway.

In any case, this discussion is predicated on the assumption that the
operations involving the bitmap are a significant fraction of the total
time, which I think is quite uncertain. Until we build it and profile
it, we won't know that.

regards, tom lane

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Greg Stark 2004-01-28 15:09:34 Re: Question about indexes
Previous Message Simon Riggs 2004-01-28 14:56:40 Re: Write cache