Greg Stark <gsstark@mit.edu> writes:
> Tom Lane <tgl@sss.pgh.pa.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