Greg Stark <[EMAIL PROTECTED]> writes: > Tom Lane <[EMAIL PROTECTED]> 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 ---------------------------(end of broadcast)--------------------------- TIP 4: Don't 'kill -9' the postmaster